1 1
2 1
3 2
4 3
5 4
6 6
7 8
8 11
9 14
10 18
11 24
12 30
13 38
14 48
15 60
16 75
17 92
18 114
19 140
20 170
21 208
22 252
23 304
24 366
25 439
26 526
27 626
28 744
29 884
30 1044
31 1232
32 1451
33 1704
34 1998
35 2336
36 2730
37 3182
38 3700
39 4300
40 4986
41 5772
42 6672
43 7700
44 8876
45 10212
46 11736
47 13472
48 15438
49 17673
50 20207
51 23076
52 26322
53 29988
54 34134
55 38808
56 44072
57 50008
58 56682
59 64184
60 72612
61 82070
62 92680
63 104560
64 117867
65 132760
66 149400
67 167996
68 188758
69 211920
70 237744
71 266512
72 298554
73 334202
74 373838
75 417902
76 466836
77 521152
78 581412
79 648224
80 722266
81 804254
82 895014
83 995432
84 1106448
85 1229148
86 1364684
87 1514316
88 1679436
89 1861548
90 2062332
91 2283568
92 2527224
93 2795488
94 3090672
95 3415344
96 3772302
97 4164578
98 4595497
99 5068632
100 5587941
101 6157700
102 6782508
103 7467464
104 8218050
105 9040224
106 9940482
107 10925848
108 12004014
109 13183238
110 14472520
111 15881692
112 17421288
113 19102812
114 20938728
115 22942512
116 25128802
117 27513364
118 30113388
119 32947424
120 36035460
121 39399277
122 43062326
123 47049972
124 51389664
125 56111016
126 61246128
127 66829520
128 72898539
129 79493608
130 86658156
131 94439176
132 102887352
133 112057312
134 122008020
135 132802908
136 144510534
137 157204684
138 170964720
139 185876372
140 202031792
141 219530208
142 238478472
143 258991504
144 281193114
145 305216244
146 331203986
147 359310354
148 389700618
149 422552612
150 458057418
151 496420280
152 537861748
153 582618492
154 630944928
155 683114048
156 739418676
157 800173430
158 865715640
159 936407196
160 1012636314
161 1094819200
162 1183402338
163 1278863996
164 1381716942
165 1492510896
166 1611834372
167 1740318096
168 1878637584
169 2027516127
170 2187728260
171 2360102824
172 2545527372
173 2744951508
174 2959390980
175 3189932984
176 3437740044
177 3704055432
178 3990208662
179 4297620968
180 4627811916
181 4982405054
182 5363135552
183 5771857708
184 6210551736
185 6681333176
186 7186461312
187 7728348456
188 8309570288
189 8932875856
190 9601199928
191 10317674112
192 11085639438
193 11908661186
194 12790541946
195 13735337448
196 14747372955
197 15831260100
198 16991915976
199 18234581288
200 19564842077
201 20988651832
202 22512353202
203 24142704288
204 25886904156
205 27752620428
206 29748019232
207 31881795504
208 34163207682
209 36602111520
210 39208997088
211 41995030124
212 44972091930
213 48152824560
214 51550678044
215 55179959632
216 59055887742
217 63194646016
218 67613444206
219 72330581236
220 77365509480
221 82738907560
222 88472753940
223 94590405680
224 101116682728
225 108077955074
226 115502238702
227 123419292808
228 131860724424
229 140860102094
230 150453070544
231 160677476160
232 171573498738
233 183183789772
234 195553621164
235 208731038112
236 222767025948
237 237715684480
238 253634408784
239 270584087008
240 288629304516
241 307838560850
242 328284500301
243 350044152674
244 373199192898
245 397836209188
246 424046988828
247 451928824264
248 481584828512
249 513124274136
250 546662949876
251 582323535736
252 620236002480
253 660538027296
254 703375439864
255 748902690360
256 797283338475
257 848690578940
258 903307789272
259 961329109360
260 1022960054908
261 1088418160596
262 1157933665908
263 1231750230096
264 1310125689720
265 1393332863652
266 1481660390944
267 1575413622612
268 1674915560196
269 1780507843156
270 1892551794804
271 2011429516352
272 2137545050342
273 2271325603040
274 2413222825734
275 2563714178344
276 2723304356784
277 2892526799198
278 3071945275740
279 3262155557728
280 3463787186352
281 3677505323948
282 3904012708704
283 4144051721924
284 4398406549608
285 4667905470288
286 4953423261672
287 5255883731552
288 5576262389466
289 5915589247315
290 6274951781772
291 6655498047172
292 7058439942126
293 7485056666116
294 7936698343734
295 8414789841720
296 8920834789242
297 9456419799912
298 10023218928162
299 10622998340896
300 11257621238514
301 11929053042976
302 12639366833088
303 13390749077052
304 14185505657652
305 15026068204120
306 15915000759876
307 16855006776716
308 17848936488096
309 18899794653136
310 20010748684032
311 21185137214896
312 22426479089940
313 23738482814858
314 25125056494998
315 26590318268448
316 28138607289168
317 29774495244852
318 31502798467956
319 33328590675768
320 35257216325146
321 37294304663592
322 39445784483904
323 41717899616336
324 44117225212890
325 46650684826922
326 49325568376452
327 52149550996876
328 55130712818814
329 58277559768832
330 61599045382992
331 65104593713684
332 68804123383508
333 72708072820228
334 76827426771240
335 81173744101872
336 85759186982928
337 90596551543346
338 95699299997151
339 101081594385060
340 106758331972020
341 112745182379136
342 119058626558136
343 125715997648528
344 132735523874156
345 140136373526112
346 147938702121018
347 156163701909560
348 164833653766356
349 173971981616246
350 183603309518640
351 193753521506668
352 204449824367244
353 215720813423676
354 227596541520888
355 240108591376656
356 253290151374526
357 267176095053984
358 281803064423076
359 297209557271120
360 313436018703276
361 330524937029877
362 348520944304006
363 367470921657050
364 387424109641584
365 408432223911400
366 430549576378500
367 453833202158144
368 478342992572984
369 504141834457644
370 531295756131132
371 559874080241696
372 589949583880128
373 621598666314206
374 654901524584248
375 689942337448152
376 726809457994992
377 765595615323448
378 806398125747600
379 849319113880004
380 894465744165400
381 941950463253088
382 991891253684160
383 1044411899539712
384 1099642264450062
385 1157718582604224
386 1218783763354306
387 1282987709979928
388 1350487653357030
389 1421448501068036
390 1496043202758264
391 1574453132496720
392 1656868488761571
393 1743488713015224
394 1834522927620498
395 1930190393967488
396 2030720991782760
397 2136355720457798
398 2247347223547488
399 2363960337358016
400 2486472664679517
401 2615175174961628
402 2750372831921736
403 2892385249913824
404 3041547380345354
405 3198210229413060
406 3362741608687344
407 3535526919822928
408 3716969975053308
409 3907493855087978
410 4107541805876052
411 4317578176182708
412 4538089397670216
413 4769585009361600
414 5012598728529360
415 5267689569906408
416 5535443015563842
417 5816472237528424
418 6111419375429136
419 6420956871819016
420 6745788867451104
421 7086652659273806
422 7444320223899492
423 7819599809322912
424 8213337598051818
425 8626419444528580
426 9059772690271440
427 9514368060164272
428 9991221643173644
429 10491396961462512
430 11016007131593736
431 11566217121821728
432 12143246109749598
433 12748369944504530
434 13382923718239264
435 14048304451482600
436 14745973897219506
437 15477461469127232
438 16244367298991580
439 17048365429048376
440 17891207145068328
441 18774724456121982
442 19700833727561940
443 20671539473485304
444 21688938315760740
445 22755223116811692
446 23872687293259064
447 25043729318546460
448 26270857422428136
449 27556694495721660
450 28903983209222910
451 30315591355650120
452 31794517424480438
453 33343896419314480
454 34967005928021268
455 36667272456787648
456 38448278038831368
457 40313767129648826
458 42267653800940310
459 44314029245691396
460 46457169607865232
461 48701544149998612
462 51051823773272640
463 53512889904982784
464 56089843768437970
465 58788016051881792
466 61612976992950054
467 64570546896108776
468 67666807101423228
469 70908111423235168
470 74301098078906656
471 77852702127780844
472 81570168441616572
473 85461065229203680
474 89533298137715040
475 93795124955140628
476 98255170938853200
477 102922444796158980
478 107806355344337904
479 112916728877861120
480 118263827272548420
481 123858366857313364
482 129711538084724810
483 135835026034106496
484 142241031781270599
485 148942294670689160
486 155952115527599142
487 163284380848368680
488 170953588010062578
489 178974871540712248
490 187364030493835170
491 196137556973252632
492 205312665854708748
493 214907325753789036
494 224940291291247480
495 235431136708622928
496 246400290889918368
497 257869073846139008
498 269859734722988136
499 282395491394008652
500 295500571703092708
501 309200256424417776
502 323520924009299436
503 338490097192646128
504 354136491534907056
505 370490065977544452
506 387582075494533984
507 405445125924274110
508 424113231070109760
509 443621872162137780
510 464008059774832104
511 485310398300219344
512 507569153079793387
513 530826320302077592
514 555125699777957118
515 580512970708769312
516 607035770568255480
517 634743777223703232
518 663688794425442592
519 693924840800974956
520 725508242493720156
521 758497729592408396
522 792954536503273164
523 828942506422035188
524 866528200070575684
525 905781008867852464
526 946773272711852424
527 989580402557520064
528 1034281007980508664
529 1080957029925866137
530 1129693878847905500
531 1180580578455080184
532 1233709915283278176
533 1289178594327637192
534 1347087400973949564
535 1407541369479388056
536 1470649958260559204
537 1536527232259502040
538 1605292052666617818
539 1677068274291007704
540 1751984950880444292
541 1830176548703428694
542 1911783168720101224
543 1996950777679077628
544 2085831448491052710
545 2178583610245115416
546 2275372308244838496
547 2376369474458086844
548 2481754208788830126
549 2591713071594326068
550 2706440387888915748
551 2826138563690028144
552 2951018414982034992
553 3081299509790913664
554 3217210523879722342
555 3358989610597723080
556 3506884785433633452
557 3661154325845381716
558 3822067186961226240
559 3989903433767907832
560 4164954690427823280
561 4347524607388690896
562 4537929346975391958
563 4736498088181898024
564 4943573551404657504
565 5159512543889973852
566 5384686526696167180
567 5619482204000877808
568 5864302135617374376
569 6119565373613128364
570 6385708123960974768
571 6663184434187167332
572 6952466908014716680
573 7254047448042294144
574 7568438027534726544
575 7896171492442749264
576 8237802394812564570
577 8593907858787012674
578 8965088480448969035
579 9351969262800774532
580 9755200587223297116
581 10175459222811151424
582 10613449375028091084
583 11069903775184493400
584 11545584812293719678
585 12041285708921348568
586 12557831742704186226
587 13096081515274380504
588 13656928270392868878
589 14241301263162163264
590 14850167182255183208
591 15484531627174298364
592 16145440642625249274
593 16833982312169506844
594 17551288413400006872
595 18298536136965487584
596 19076949871859498618
597 19887803059474902928
598 20732420119018877712
599 21612178446982666032
600 22528510493453833506
601 23482905918166653674
602 24476913829291480672
603 25512145108073446216
604 26590274822548798008
605 27713044733680864692
606 28882265897385952596
607 30099821366045286128
608 31367668993227598004
609 32687844345490594272
610 34062463725265972620
611 35493727308981377984
612 36983922404726244276
613 38535426833922445550
614 40150712441629813188
615 41832348740279930520
616 43583006691808845984
617 45405462633345004364
618 47302602351789210960
619 49277425312824271028
620 51333049050091712064
621 53472713720480440656
622 55699786831692775608
623 58017768148470946144
624 60430294784105849940
625 62941146484088080669
626 65554251109005594730
627 68273690324058679776
628 71103705502823101986
629 74048703853171019656
630 77113264773547258272
631 80302146448090326872
632 83620292689401825872
633 87072840038078388376
634 90665125128451877130
635 94402692330329504832
636 98291301676868876292
637 102336937089095862102
638 106545814907948927144
639 110924392745123186832
640 115479378664398095130
641 120217740705544163644
642 125146716763346834904
643 130273824834732634460
644 135606873647442509888
645 141153973684189871664
646 146923548616731211848
647 152924347164796390544
648 159165455395362363114
649 165656309478301521360
650 172406708915017669938
651 179426830257266140160
652 186727241333971129956
653 194318916004494814740
654 202213249457458003428
655 210422074074901798536
656 218957675882280452510
657 227832811605501650092
658 237060726356990878848
659 246655171973526397992
660 256630426029408972816
661 267001311549362456702
662 277783217446418471868
663 288992119710946281048
664 300644603377903797300
665 312757885300346891136
666 325349837758227753084
667 338439012932530973808
668 352044668275868294856
669 366186792811738915360
670 380886134395801652568
671 396164227973688182288
672 412043424871087063056
673 428546923153097621858
674 445698799091149645898
675 463524039777127523966
676 482048576925737807133
677 501299321907586375620
678 521304202056934024812
679 542092198299635843344
680 563693384148354587476
681 586138966113803630520
682 609461325582467003136
683 633694062213012307160
684 658872038905439993880
685 685031428398890222028
686 712209761555994427872
687 740445977393662649884
688 769780474922290000812
689 800255166857534696792
690 831913535271034105632
691 864800689248749174828
692 898963424628010463922
693 934450285886804538816
694 971311630261403206476
695 1009599694171062536528
696 1049368662031265196084
697 1090674737539797521556
698 1133576217522860808406
699 1178133568431455691828
700 1224409505581382970840
701 1272469075233436841780
702 1322379739613707290372
703 1374211464977346719272
704 1428036812822740437388
705 1483931034366690097728
706 1541972168395037564382
707 1602241142607110615840
708 1664821878576423283224
709 1729801400454294481646
710 1797269947547396996720
711 1867321090904745738688
712 1940051854054300277358
713 2015562838034146964224
714 2093958350868218319648
715 2175346541641640283792
716 2259839539336096483892
717 2347553596591115799072
718 2438609238562844614824
719 2533131417057738461920
720 2631249670124676339180
721 2733098287295253639616
722 2838816480668508772693
723 2948548562043010203556
724 3062444126306156390490
725 3180658241297706590188
726 3303351644371920696462
727 3430690945890345415544
728 3562848839885167685616
729 3700004322141205197998
730 3842342915953046625684
731 3990056905822537425200
732 4143345579370830301332
733 4302415477748509098326
734 4467480654836885070424
735 4638762945543523922460
736 4816492243505293818168
737 5000906788522831485088
738 5192253464061280526100
739 5390788105163452510172
740 5596775817133278472076
741 5810491305359467866896
742 6032219216661778848048
743 6262254492555213979280
744 6500902734840737384256
745 6748480583944896205476
746 7005316110444933034686
747 7271749220230651786536
748 7548132073769487078552
749 7834829519956865244608
750 8132219545050161660232
751 8440693737201268010624
752 8760657767120031869168
753 9092531885418709807176
754 9436751437205969795196
755 9793767394518021739488
756 10164046907194121336208
757 10548073872823975019582
758 10946349526415579113372
759 11359393050453651620928
760 11787742206041196952152
761 12231953985839871682476
762 12692605289548636265664
763 13170293622684855466288
764 13665637819457447722944
765 14179278790547956548360
766 14711880296642582374272
767 15264129748586203452752
768 15836739035058396054030
769 16430445378701339574530
770 17046012221660328855744
771 17684230141529534669316
772 18345917798728522255302
773 19031922916369030834500
774 19743123293706612993672
775 20480427854307933651632
776 21244777730101976009910
777 22037147382521980859744
778 22858545761984835743634
779 23710017506995830378128
780 24592644184209146528472
781 25507545570818378706528
782 26455880980696674540592
783 27438850635752847294444
784 28457697084018131653155
785 29513706666028058599896
786 30608211031115435685576
787 31742588705283529955660
788 32918266712383361037034
789 34136722250375685919536
790 35399484424516649146272
791 36708136039366413450976
792 38064315451582367813160
793 39469718485522752826948
794 40926100413752940607590
795 42435278004615035127624
796 43999131639092159975208
797 45619607499271792724020
798 47298719830787738169792
799 49038553281698104433760
800 50841265320336840787453
801 52709088734759168379468
802 54644334216486711676110
803 56649393031346258996080
804 58726739780287140258600
805 60878935253156105496960
806 63108629378505466936912
807 65418564272610360232044
808 67811577390974136151386
809 70290604785707425696780
810 72858684472276348950300
811 75518959909228716936980
812 78274683594624176021744
813 81129220783014947646784
814 84086053326948452569416
815 87148783647091736106224
816 90321138835210203565500
817 93606974894370135862384
818 97010281120875680618242
819 100535184632596732732064
820 104185955048494526814276
821 107967009324306829696164
822 111882916749514749887196
823 115938404110878289791320
824 120138361027998083197832
825 124487845466536613995032
826 128992089434913465965856
827 133656504870476241976376
828 138486689721341789467536
829 143488434230301399695798
830 148667727427389095894200
831 154030763837923901851708
832 159583950413055549955266
833 165333913690068577222460
834 171287507189932199471640
835 177451819059823304583312
836 183834179968597304078800
837 190442171263436775809248
838 197283633396171129191124
839 204366674628031960036496
840 211699680021888904705248
841 219291320731299627656047
842 227150563596005439212374
843 235286681053811424500820
844 243709261379106786099924
845 252428219258607978621820
846 261453806715244323456288
847 270796624391453375865704
848 280467633203511939006922
849 290478166378898267858632
850 300839941889062345288386
851 311565075290374404076192
852 322666092986427254567952
853 334155945925286246827070
854 346048023745711884318880
855 358356169386824753202096
856 371094694176141033610284
857 384278393411379577435372
858 397922562451929192775056
859 412043013336367466026724
860 426656091942940747255848
861 441778695710449549320480
862 457428291937534604460528
863 473622936678927081650368
864 490381294257812363000478
865 507722657414060754177876
866 525666968108701409274610
867 544234839005657732494502
868 563447575652424556604160
869 583327199382049982809088
870 603896470959488249666232
871 625178914996115525459944
872 647198845156948320956066
873 669981390185875150243420
874 693552520775006931487392
875 717939077305070818357056
876 743168798484616900220748
877 769270350916677841853798
878 796273359622418969101264
879 824208439552241661968316
880 853107228115756475282856
881 883002418763025508579804
882 913927795650486892817154
883 945918269426018655174380
884 979009914168675963472260
885 1013240005519745293533936
886 1048647060042902881701804
887 1085270875852443810530224
888 1123152574549762955794116
889 1162334644509521501018368
890 1202860985558223401574772
891 1244776955089256418970776
892 1288129415659823463786528
893 1332966784116602817846656
894 1379339082298432186156980
895 1427297989365812233825128
896 1476896895808571787007976
897 1528190959184630966815968
898 1581237161644440926866302
899 1636094369297371619723072
900 1692823393478063401949190
901 1751487053972555714813244
902 1812150244265858576456856
903 1874879998874541206406464
904 1939745562829879044288294
905 2006818463379127292391672
906 2076172583974577293901232
907 2147884240622204144217716
908 2222032260663931183758756
909 2298698064069821644448100
910 2377965747318861883168800
911 2459922169949425929152800
912 2544657043863010324144776
913 2632263025467403003001328
914 2722835810748102696444050
915 2816474233359538810122024
916 2913280365830457520636746
917 3013359623980741097958208
918 3116820874649916474843084
919 3223776546840688282891640
920 3334342746384004175790608
921 3448639374235428267664600
922 3566790248515965478487898
923 3688923230413948223694944
924 3815170354068169737130560
925 3945667960556129383184546
926 4080556836115047017165512
927 4219982354727209387770096
928 4364094625205235310520082
929 4513048642916990781631228
930 4667004446294154773332224
931 4826127278272834071184620
932 4990587752819155207117070
933 5160562026697427757834192
934 5336231976643279045296132
935 5517785382109110585405088
936 5705416113754325405396700
937 5899324327858026771137690
938 6099716666837298079826016
939 6306806466059744398582036
940 6520813967144713992146208
941 6741966537953527846830292
942 6970498899475131125018436
943 7206653359819848971955600
944 7450680055540384560773244
945 7702837200505845582945888
946 7963391342561432460392304
947 8232617628213472504786920
948 8510800075586746097895456
949 8798231855908528952979484
950 9095215583781475271779628
951 9402063616515397325989260
952 9719098362796163189996880
953 10046652600978343984881836
954 10385069807296901774115612
955 10734704494302126260529792
956 11095922559831210978221616
957 11469101646839314387416048
958 11854631514422687170880160
959 12252914420376471999168608
960 12664365515640103801568580
961 13089413250993867156988833
962 13528499796381110604466116
963 13982081473241885106103896
964 14450629200255375299098422
965 14934628952900436428179208
966 15434582237255848189848192
967 15951006578474558306467688
968 16484436024379224403808943
969 17035421664639784371896880
970 17604532166007602596392036
971 18192354324094965026915608
972 18799493632203341360792766
973 19426574867718909564480544
974 20074242696609360002241456
975 20743162296571975142544340
976 21434019999399430679133042
977 22147523953146698215892828
978 22884404804699861591462280
979 23645416403365604494667784
980 24431336526118599725548282
981 25242967625163046103150164
982 26081137598484173641725852
983 26946700584085686345484912
984 27840537778629852906939180
985 28763558281218304458330948
986 29716699963073573297865908
987 30700930363904026220487936
988 31717247615758127562389112
989 32766681395197930939349952
990 33850293904646363986298352
991 34969180883788257051616592
992 36124472651931196677451424
993 37317335182259177559485800
994 38548971208939706012212416
995 39820621368073495935689632
996 41133565373505217090843464
997 42489123228543930975403502
998 43888656474672904686517668
999 45333569478360453792627196
1000 46825310757116357802028548