1 1
2 2
3 1
4 4
5 3
6 8
7 7
8 15
9 15
10 27
11 29
12 48
13 53
14 82
15 94
16 137
17 160
18 225
19 265
20 362
21 430
22 572
23 683
24 892
25 1066
26 1370
27 1640
28 2078
29 2487
30 3117
31 3725
32 4624
33 5519
34 6791
35 8092
36 9885
37 11752
38 14263
39 16922
40 20416
41 24167
42 29007
43 34254
44 40921
45 48213
46 57345
47 67409
48 79864
49 93661
50 110565
51 129378
52 152211
53 177720
54 208435
55 242841
56 283982
57 330172
58 385048
59 446772
60 519695
61 601810
62 698346
63 807153
64 934477
65 1078081
66 1245439
67 1434250
68 1653485
69 1900860
70 2187108
71 2510097
72 2882686
73 3303003
74 3786497
75 4331767
76 4957324
77 5662539
78 6469625
79 7379025
80 8417451
81 9586876
82 10919379
83 12419090
84 14124570
85 16042787
86 18220175
87 20667498
88 23440611
89 26555314
90 30078859
91 34033500
92 38500307
93 43509870
94 49159850
95 55491569
96 62622735
97 70608195
98 79589941
99 89639934
100 100929358
101 113551768
102 127713611
103 143535339
104 161266026
105 181059683
106 203216653
107 227932736
108 255570108
109 286376132
110 320787614
111 359115589
112 401886567
113 449490061
114 502560604
115 561583847
116 627324401
117 700385675
118 781688468
119 871980197
120 972369363
121 1083778688
122 1207542224
123 1344796017
124 1497144483
125 1665982869
126 1853239823
127 2060624472
128 2290454128
129 2544817742
130 2826497658
131 3138041846
132 3482789043
133 3863840469
134 4285200226
135 4750635850
136 5264945830
137 5832699186
138 6459642645
139 7151307250
140 7914570885
141 8756118323
142 9684174997
143 10706807760
144 11833846685
145 13075011324
146 14442041275
147 15946630703
148 17602788794
149 19424566406
150 21428668907
151 23631955675
152 26054332746
153 28716003578
154 31640669702
155 34852512395
156 38379731364
157 42251233405
158 46500545397
159 51162183158
160 56275976308
161 61883092119
162 68030812518
163 74768183412
164 82151291883
165 90238508372
166 99096314207
167 108794105895
168 119410626856
169 131028298259
170 143740318871
171 157644483177
172 172851016436
173 189475843459
174 207649231291
175 227508466539
176 249207390751
177 272908440444
178 298793165211
179 327053587909
180 357903803027
181 391570608754
182 428306299569
183 468378517958
184 512084362472
185 559739411865
186 611693280508
187 668317761760
188 730023983811
189 797249615814
190 870477788279
191 950223312373
192 1037053543990
193 1131573561479
194 1234449180366
195 1346391032607
196 1468179954984
197 1600649923546
198 1744716060152
199 1901356371973
200 2071642657415
201 2256721001232
202 2457845884851
203 2676359403122
204 2913728914373
205 3171524944887
206 3451462763153
207 3755378943337
208 4085277282800
209 4443304019575
210 4831798555780
211 5253267329987
212 5710439875272
213 6206241361006
214 6743854564889
215 7326691134398
216 7958460114083
217 8643137993831
218 9385044522840
219 10188811638305
220 11059467371062
221 12002403802787
222 13023469957324
223 14128938968291
224 15325610973459
225 16620779722698
226 18022346599821
227 19538786982749
228 21179276644613
229 22953658239642
230 24872581506278
231 26947470332434
232 29190678338513
233 31615457099816
234 34236128870459
235 37068056644460
236 40127836019052
237 43433267906819
238 47003571761998
239 50859361941587
240 55022884781146
241 59517999771892
242 64370443305367
243 69607816039521
244 75259876456924
245 81358536071022
246 87938186320532
247 95035703533494
248 102690813148178
249 110946106672447
250 119847447692234
251 129444003476325
252 139788697776254
253 150938260139858
254 162953731166807
255 175900533081873
256 189849033788909
257 204874642866448
258 221058441542908
259 238487308905767
260 257254625855079
261 277460437053530
262 299212237893638
263 322625178615977
264 347822944444193
265 374938009246179
266 404112620315988
267 435499110050826
268 469260998265534
269 505573371679091
270 544624118252026
271 586614385686580
272 631759964157753
273 680291836658462
274 732457728514988
275 788522764336187
276 848771205000984
277 913507228056285
278 983056875535299
279 1057768977039776
280 1138017334642740
281 1224201810694971
282 1316750779350727
283 1416122404196808
284 1522807389732747
285 1637330477416250
286 1760253534570523
287 1892177301500530
288 2033744859988892
289 2185643668598203
290 2348609458302683
291 2523428598169401
292 2710942471584271
293 2912050220366334
294 3127713661729181
295 3358960465349907
296 3606889678845924
297 3872675399664660
298 4157572985278380
299 4462923290186645
300 4790159646536957
301 5140812745866544
302 5516518486682295
303 5919023591139809
304 6350194428089656
305 6812023466968048
306 7306639198311957
307 7836313540545237
308 8403472995284426
309 9010707137862869
310 9660781161737495
311 10356645600839450
312 11101450436513441
313 11898556218973896
314 12751549931856594
315 13664257701709732
316 14640762639286271
317 15685419350556693
318 16802874000909961
319 17998080868530869
320 19276324908217208
321 20643240618782783
322 22104837417171913
323 23667521126406115
324 25338122508831760
325 27123921719996881
326 29032680392877408
327 31072669446789136
328 33252705162325414
329 35582180783748436
330 38071107078101903
331 40730148224564712
332 43570667411660407
333 46604767568889216
334 49845342623313544
335 53306123698421781
336 57001736726870991
337 60947754819242981
338 65160763014553374
339 69658417608748146
340 74459518919125686
341 79584078460450344
342 85053400705310700
343 90890159105112053
344 97118487947180927
345 103764068340502232
346 110854231402784067
347 118418055468433083
348 126486481986949323
349 135092425364194802
350 144270903119507350
351 154059159943250726
352 164496813845078358
353 175625996203499070
354 187491515844610935
355 200141017074418288
356 213625163858924074
357 227997818070434363
358 243316246197964417
359 259641320308035603
360 277037750002655518
361 295574308895382041
362 315324094856502060
363 336364785140704899
364 358778928318241141
365 382654231565840543
366 408083888083570776
367 435166900478957651
368 464008447917130698
369 494720249995207347
370 527420978372138015
371 562236666052261767
372 599301168797701083
373 638756625321424002
374 680753974406049498
375 725453472155434556
376 773025271435146525
377 823650003055610266
378 877519424920203259
379 934837074819269691
380 995818997531196121
381 1060694477805437684
382 1129706854618327447
383 1203114343925564889
384 1281190950339853291
385 1364227390348910410
386 1452532112869032382
387 1546432334867419812
388 1646275183566113014
389 1752428857792047261
390 1865283906075557162
391 1985254528591872024
392 2112780007034722767
393 2248326163727561347
394 2392386960972062168
395 2545486135816129487
396 2708178988600845676
397 2881054213994558812
398 3064735900713315785
399 3259885581790978540
400 3467204469950063386
401 3687435752703878935
402 3921367090636000334
403 4169833185848465247
404 4433718573500189813
405 4713960495358927789
406 5011552018383093940
407 5327545248740853301
408 5663054815035073693
409 6019261462157244087
410 6397415940993946295
411 6798843025931489407
412 7224945857587357937
413 7677210432722591031
414 8157210451765596739
415 8666612335373638805
416 9207180634316237199
417 9780783633015427358
418 10389399385790506301
419 11035121974465130019
420 11720168242114895240
421 12446884779326468721
422 13217755434511246125
423 14035409111719175614
424 14902628145365622536
425 15822357001729428563
426 16797711615680803626
427 17831989098222772308
428 18928678143608755001
429 20091469856628504664
430 21324269350473853714
431 22631207820044262820
432 24016655464185005171
433 25485234945220145544
434 27041835783888095061
435 28691629360748191595
436 30440084948421427050
437 32292986427621652165
438 34256450139344645202
439 36336943507217490308
440 38541304912253395925
441 40876764434190006315
442 43350965973539493466
443 45971990347814152201
444 48748379910079319619
445 51689164261673527985
446 54803887643565590596
447 58102637555630512758
448 61596075227089693196
449 65295467463891724804
450 69212720537681199036
451 73360415617666205193
452 77751846454251108485
453 82401058790302607100
454 87322892256155433865
455 92533024197802833733
456 98048016244849097301
457 103885363040265591328
458 110063543992467477804
459 116602077443363867761
460 123521578170561324320
461 130843817588012875655
462 138591787624942118816
463 146789767617019867471
464 155463395255556769134
465 164639740897436521410
466 174347386352088911139
467 184616507416073965474
468 195478961347046633003
469 206968378514664842157
470 219120259500987571260
471 231972076854108528604
472 245563382854055586989
473 259935922460149042569
474 275133752891458219556
475 291203368974347380119
476 308193835807954472807
477 326156927845832555776
478 345147276050899251456
479 365222522185728986549
480 386443482009264139042
481 408874316405494093138
482 432582712337329556317
483 457640072614598531977
484 484121716500399166078
485 512107090108174244934
486 541679988754281101579
487 572928790182145382669
488 605946700973590419977
489 640832015027682499688
490 677688386584587733535
491 716625116639860083404
492 757757455400503869728
493 801206919594473936445
494 847101627471698502315
495 895576650276062478872
496 946774383227097412594
497 1000844934760560651413
498 1057946537282324250150
499 1118245978156963211475
500 1181919054417360783552
501 1249151049891926544324
502 1320137238485171744957
503 1395083412287073568263
504 1474206438515327093782
505 1557734843949086038960
506 1645909431147116031052
507 1738983925097233813289
508 1837225654900920840382
509 1940916269134250696728
510 2050352489823913421572
511 2165846903680726676910
512 2287728795890214270468
513 2416345025111961571594
514 2552060945376164748181
515 2695261373547714045795
516 2846351608465399890338
517 3005758500455901770702
518 3173931577782183037298
519 3351344228767469750817
520 3538494946642072634831
521 3735908635909660742515
522 3944137987806433590038
523 4163764923721040534108
524 4395402114716676202042
525 4639694576112329713159
526 4897321345877910308379
527 5168997245909589798207
528 5455474735602485222524
529 5757545856919209889056
530 6076044281087090527354
531 6411847456280431276298
532 6765878867194093336010
533 7139110406051473999002
534 7532564866789309233473
535 7947318562181451835486
536 8384504076548249658317
537 8845313154068961062282
538 9330999736321900372752
539 9842883149365554111358
540 10382351455043597154863
541 10950864967168111415735
542 11549959948409244749758
543 12181252488937125388597
544 12846442583884153757823
545 13547318411121229210331
546 14285760827758620175356
547 15063748087375366199485
548 15883360797842108902391
549 16746787122321125158509
550 17656328244883925784651
551 18614404103987359344101
552 19623559416955817893453
553 20686469999453426693669
554 21805949404944294178931
555 22984955888962723830200
556 24226599725197674210138
557 25534150879156758547238
558 26911047068589555080169
559 28360902217495582635786
560 29887515335256285414221
561 31494879828905489904275
562 33187193282637453476179
563 34968867713898782695995
564 36844540342940813507575
565 38819084886668241936062
566 40897623416674888585537
567 43085538793965991416784
568 45388487723529826564469
569 47812414443113827623111
570 50363565092920143689277
571 53048502782643567303169
572 55874123406423825652868
573 58847672224436583005623
574 61976761265883981231502
575 65269387574667985330799
576 68733952357057168266674
577 72379281055472744479884
578 76214644412647145717731
579 80249780553435671730329
580 84494918153904715853911
581 88960800728475380241337
582 93658712110581443678550
583 98600503161496685847727
584 103798619789132409732448
585 109266132315751797427681
586 115016766283295033606950
587 121064934740010097338971
588 127425772104576164074887
589 134115169656664478190823
590 141149812758269695015819
591 148547219860557427959153
592 156325783409417938072630
593 164504812710877448538177
594 173104578879187721022758
595 182146361935814981535429
596 191652500192621871174001
597 201646441995261379983043
598 212152799971466452994984
599 223197407868850895275016
600 234807380139293413278606
601 247011174363992949645133
602 259838656689741911836739
603 273321170380937954442248
604 287491607672538583907172
605 302384485039963748556692
606 318036022087095965750660
607 334484224181020146306504
608 351768969051999680573973
609 369932097501230076805507
610 389017508453739632300214
611 409071258514259553706553
612 430141666283966857354242
613 452279421612716407199933
614 475537700067007314649862
615 499972282806749482275642
616 525641682175385508177652
617 552607273216694496297137
618 580933431449285122609525
619 610687677134346624300620
620 641940826396448882140289
621 674767149457369087780272
622 709244536374057870778607
623 745454670567500244363069
624 783483210567668030700306
625 823419980290686658428065
626 865359168310502951088664
627 909399536473374415569325
628 955644638357828267207211
629 1004203047963700697462284
630 1055188599176826531067195
631 1108720636431658025295229
632 1164924277166179304785907
633 1223930686533753077950075
634 1285877365018278530132460
635 1350908449463684121086615
636 1419175028220733989308506
637 1490835470972957853994508
638 1566055774006274377867966
639 1645009921539705899380774
640 1727880263948776510304245
641 1814857913559820198403629
642 1906143158919721253104768
643 2001945898285861233564166
644 2102486093320152466892944
645 2207994243804718995184004
646 2318711884449454785860294
647 2434892104688612481966651
648 2556800092630607890423893
649 2684713704145208429259807
650 2818924058354518722047288
651 2959736160607040281676292
652 3107469554312444024667249
653 3262459002820265792475680
654 3425055202841174380077970
655 3595625530707575084875907
656 3774554823103850462786232
657 3962246193687038572346052
658 4159121887371474316161005
659 4365624173833656986233945
660 4582216282166675831439752
661 4809383378388368756201765
662 5047633587902032677057827
663 5297499064775334842998849
664 5559537110120603813584446
665 5834331341618396480868493
666 6122492916668049036760992
667 6424661811399444558741063
668 6741508158247810924239320
669 7073733644535638018966840
670 7422072975000738986412578
671 7787295400943476496829410
672 8170206319190154807401363
673 8571648943795297173545808
674 8992506053960353090075692
675 9433701821363857351919444
676 9896203720685654071279892
677 10381024526817110814620892
678 10889224402871654292257133
679 11421913082811226274038647
680 11980252153163666100915655
681 12565457437999419023330846
682 13178801492034712509932546
683 13821616206414087843621319
684 14495295532465743520004101
685 15201298328401534351601220
686 15941151334718525895419175
687 16716452283730393037985483
688 17528873149489335681787937
689 18380163544024013393936758
690 19272154266701749206828425
691 20206761013182046549794906
692 21185988251364820311098510
693 22211933271390122861494285
694 23286790417739580202155165
695 24412855511138447513984104
696 25592530469011413232078059
697 26828328132890136227580471
698 28122877312289472054138601
699 29478928054211338437080399
700 30899357148623136173948260
701 32387173879897896667037250
702 33945526035464827452943444
703 35577706182558724918208876
704 37287158225296616301760949
705 39077484253950790671771405
706 40952451699710865902352169
707 42916000807870986472470429
708 44972252443890897702659754
709 47125516246427603603293091
710 49380299143042094273756843
711 51741314243940200613822827
712 54213490130815930709616370
713 56801980557529177437233920
714 59512174581167347002949885
715 62349707141715591652010257
716 65320470110493690130730264
717 68430623827207293999351021
718 71686609147518183107409231
719 75095160022745669712164274
720 78663316635500211882242319
721 82398439114779265753292443
722 86308221856385364369146674
723 90400708474280907490734893
724 94684307410974839389890982
725 99167808234820913594298399
726 103860398654749072603352916
727 108771682282770999583237576
728 113911697177415025268339825
729 119290935201105618332535320
730 124920362227501088377390197
731 130811439234709777487611328
732 136976144323500546432764549
733 143426995699583325681509335
734 150177075662441960162053335
735 157240055643222258791963092
736 164630222337810363790630481
737 172362504981326103781508614
738 180452503814129853351707038
739 188916519789608802405751037
740 197771585578141138814900338
741 207035497921891711836833721
742 216726851399502440082094760
743 226865073660094293666920102
744 237470462190704189967218178
745 248564222681744081817108118
746 260168509060094025796494637
747 272306465260028346728212994
748 285002268807539289077181644
749 298281176294347524459058231
750 312169570823619391732713578
751 326695011510288990627843798
752 341886285125005288683550102
753 357773459971772998210772685
754 374387942095897822363632545
755 391762533920084304819824828
756 409931495413526557748926123
757 428930607900279240960373250
758 448797240620671084198869408
759 469570420161202115289265527
760 491290902876358699194607553
761 514001250427715494685291367
762 537745908574242195524297520
763 562571289349950638399372233
764 588525856774163088179355127
765 615660216242211934040161865
766 644027207754166453071067285
767 673682003142055040106976267
768 704682207466523957259622118
769 737087964757124169290887047
770 770962068281628321447424679
771 806370075533445727442174343
772 843380428138206008364429551
773 882064576884703997776216061
774 922497112098252166716728589
775 964755899579109443112093791
776 1008922222342422843295856209
777 1055080928401290000572873427
778 1103320584849299964158487066
779 1153733638504683001691154939
780 1206416583394004180473623027
781 1261470135359767801428098643
782 1318999414093237132165822219
783 1379114132900927348008934154
784 1441928796531384868458267916
785 1507562907396808519816182376
786 1576141180543532173206582127
787 1647793767734192987065052671
788 1722656491025280533362061438
789 1800871086233508574801725662
790 1882585456706834829561358938
791 1967953937826729164782054849
792 2057137572692300205639376184
793 2150304399448788075094681686
794 2247629750748688752819078164
795 2349296565846897900008396022
796 2455495715858899615054163721
797 2566426342725483234274705521
798 2682296212457130455209682301
799 2803322083247128021860301749
800 2929730089074294482596610230
801 3061756139433707944219109307
802 3199646335867993388861400180
803 3343657405990953062043885358
804 3494057155732010316411209027
805 3651124940551041670295894578
806 3815152156412564380917909918
807 3986442751331396320031090525
808 4165313758344208192491383042
809 4352095850786762229080374523
810 4547133920802066232889543439
811 4750787682032464962961725279
812 4963432297497494814901042986
813 5185459033689750400646950878
814 5417275941973440820576643277
815 5659308568403593534814498787
816 5912000693140193785246893892
817 6175815100667931840415269815
818 6451234382092758037646474886
819 6738761770826201158332395144
820 7038922013033450628243820538
821 7352262274264618790862036411
822 7679353083758505843732056313
823 8020789317955578597645146750
824 8377191224832012501351675000
825 8749205490718345916242592021
826 9137506351347064854792157958
827 9542796748929812636730830162
828 9965809537151748723580607512
829 10407308736032029409877712713
830 10868090838692736040105647290
831 11348986172145524592073764023
832 11850860314305644751919387099
833 12374615569515886742778395823
834 12921192504970946070322650602
835 13491571550512068026856107087
836 14086774664377900777381064399
837 14707867067583858944970307584
838 15355959049727123427116168496
839 16032207849108361025023717254
840 16737819610195497531327081346
841 17474051421557050747445203107
842 18242213437536926940202110308
843 19043671087053652808659284262
844 19879847373062334998189389008
845 20752225266338338753939911316
846 21662350197408755583240880783
847 22611832650588854359069697815
848 23602350864260446235126495917
849 24635653641671500654398925083
850 25713563276729711523149554592
851 26837978599417327487235008395
852 28010878145662590152159810428
853 29234323456670946084954212377
854 30510462512943018430585046728
855 31841533308388431557881044984
856 33229867570185399985728912283
857 34677894630233549890123954248
858 36188145454306557202574388848
859 37763256835225448754757362472
860 39405975756652225835411180805
861 41119163934335792443344704400
862 42905802541942186789511630049
863 44768997128852959886162229538
864 46711982737638385763096528557
865 48738129229185132451787393053
866 50850946823805432718899266364
867 53054091866950538300585031212
868 55351372828525098067354342383
869 57746756545119479784050131152
870 60244374714879379386767827687
871 62848530655079053390307968365
872 65563706332897476479764721910
873 68394569680272463189766297406
874 71345982204173741289565113594
875 74423006904042745772669659257
876 77630916508648351397820496666
877 80975202045048066034026549330
878 84461581752883865900268671007
879 88096010357718352732822872833
880 91884688717697696823235490007
881 95834073858343402819578939713
882 99950889410899980761370641448
883 104242136470223354751459537373
884 108715104888867523484723197072
885 113377385024630257366504406314
886 118236879959542565453568602943
887 123301818208939059073746575418
888 128580766940025459691713909256
889 134082645720064896462791085839
890 139816740815143133112243475498
891 145792720061235446782824176425
892 152020648330200268380498354906
893 158511003614148965433422157923
894 165274693752612289015140808752
895 172323073827814816485917108554
896 179667964254413844303535009856
897 187321669591021757420219680979
898 195296998101955629406041512220
899 203607282098697766413213005680
900 212266399091761288370901359750
901 221288793784778242716327895727
902 230689500943930282497695105998
903 240484169177055305874355692001
904 250689085658165140558506398799
905 261321201834419704587978013509
906 272398160154111431736417145946
907 283938321855628636334981918062
908 295960795858989605944065999238
909 308485468803066768245922835517
910 321533036273366843384456918290
911 335125035266881875392335428495
912 349283877942405400158008646518
913 364032886706487833964612979233
914 379396330687227379078362638332
915 395399463650013549856453646567
916 412068563411516287659338756108
917 429430972810286326677893291360
918 447515142294673603715945066211
919 466350674191006819770460000539
920 485968368717496142141128247269
921 506400271811733595200496164655
922 527679724842375737231266747187
923 549841416278195604166136639345
924 572921435390606540910474058430
925 596957328068567354822958679098
926 621988154827914956556778319305
927 648054551100197607653062107591
928 675198789889456373623338078215
929 703464846888666370985168341355
930 732898468151179525914189986678
931 763547240416029756122388501125
932 795460664189866502719632961349
933 828690229692076473525187931906
934 863289495773854029879023167754
935 899314171926070330251169435483
936 936822203495309678417687282049
937 975873860231849535526163798806
938 1016531828298220614442249962790
939 1058861305871734095043466084365
940 1102930102479590217287446438082
941 1148808742210301836140535851762
942 1196570570950788538295878699796
943 1246291867804013007271416393101
944 1298051960848077719508039467334
945 1351933347403643050759093971977
946 1408021818983030424644005817432
947 1466406591100776445263814160960
948 1527180438132396795904965553772
949 1590439833415015131074161499478
950 1656285094791031974866811360028
951 1724820535803436637143476767835
952 1796154622759451260473000642711
953 1870400137887195867483343663479
954 1947674348818757975811284148556
955 2028099184641665059034390886863
956 2111801418770106828781319479052
957 2198912858896530385754825448277
958 2289570544294282737460814459025
959 2383916950751962466780814992085
960 2482100203430948887913450214328
961 2584274297948329076485716205235
962 2690599329999061021500436038470
963 2801241733842785478952460015112
964 2916374529993188620303107718638
965 3036177582460275958549900591156
966 3160837865909343983292204057738
967 3290549743113844726677925853059
968 3425515253093770410318767221243
969 3565944410345615759117092557667
970 3712055515585488127090583947762
971 3864075478442464163613231149415
972 4022240152555965067635501887004
973 4186794683547631350423026868334
974 4357993870356098110318499846416
975 4536102540441049177637214908666
976 4721395939382187638681562911750
977 4914160135418100765087423122503
978 5114692439490694653737304219243
979 5323301841381679202938758660492
980 5540309462549825762653894184386
981 5766049026300099024712773581021
982 6000867345939664937088791408995
983 6245124831599846670745696044057
984 6499196016428781793500363583633
985 6763470102885420757696379238375
986 7038351529893100173383058481177
987 7324260561638762893737209921051
988 7621633898833543447415863970966
989 7930925313280372272554935387934
990 8252606306626103024306289237093
991 8587166794207853854298623978384
992 8935115814937470853337342098638
993 9296982268202626864515370247477
994 9673315678799826600145300908513
995 10064686990951791241951691323923
996 10471689392501180458815902270098
997 10894939170412601125741005524631
998 11335076598757263951084736380924
999 11792766860397635513795708251326
1000 12268701003634986959896441476665