0 1
1 1
2 1
3 1
4 1
5 2
6 2
7 2
8 2
9 4
10 5
11 5
12 5
13 9
14 11
15 12
16 12
17 19
18 26
19 28
20 29
21 40
22 55
23 62
24 64
25 81
26 113
27 132
28 139
29 163
30 221
31 265
32 284
33 320
34 421
35 514
36 563
37 619
38 783
39 965
40 1074
41 1169
42 1432
43 1765
44 1996
45 2167
46 2575
47 3159
48 3613
49 3931
50 4566
51 5552
52 6410
53 7006
54 7990
55 9605
56 11148
57 12259
58 13801
59 16387
60 19080
61 21108
62 23548
63 27621
64 32167
65 35790
66 39699
67 46029
68 53534
69 59850
70 66162
71 75918
72 88026
73 98796
74 109039
75 123992
76 143203
77 161178
78 177817
79 200655
80 230654
81 260088
82 287033
83 321860
84 368147
85 415498
86 458905
87 511970
88 582605
89 657597
90 726990
91 807799
92 914693
93 1031791
94 1141775
95 1264746
96 1425312
97 1605877
98 1778543
99 1965456
100 2205260
101 2480575
102 2749085
103 3032641
104 3388978
105 3804615
106 4218135
107 4647201
108 5174560
109 5796488
110 6427488
111 7074579
112 7852197
113 8775541
114 9729768
115 10701858
116 11844896
117 13206200
118 14637132
119 16090980
120 17766138
121 19760733
122 21889401
123 24053352
124 26501411
125 29407779
126 32551016
127 35755555
128 39322971
129 43536972
130 48146075
131 52866860
132 58050578
133 64133250
134 70848534
135 77766166
136 85276190
137 94020541
138 103745897
139 113829174
140 124676229
141 137200054
142 151206996
143 165827852
144 181445083
145 199319746
146 219389565
147 240481729
148 262893363
149 288321912
150 316942340
151 347218893
152 379272945
153 415335655
154 455968819
155 499220497
156 544908461
157 595900334
158 653351023
159 714852834
160 779747757
161 851641060
162 932556957
163 1019622106
164 1111476065
165 1212552293
166 1326106878
167 1448838112
168 1578395637
169 1720106174
170 1878923522
171 2051230855
172 2233331066
173 2431466465
174 2652876215
175 2893850659
176 3148918829
177 3425191907
178 3732922112
179 4068687282
180 4424744213
181 4808928323
182 5235390593
183 5701590688
184 6196956623
185 6729765033
186 7319124327
187 7964261787
188 8651180490
189 9388134266
190 10200431267
191 11090332653
192 12039822849
193 13056431753
194 14173098032
195 15396878703
196 16705205574
197 18103892282
198 19635120312
199 21313132235
200 23110429549
201 25029758469
202 27124319635
203 29418722719
204 31880443873
205 34507395332
206 37365699731
207 40494491615
208 43856598139
209 47442852524
210 51334273402
211 55589875313
212 60168926814
213 65052423656
214 70338239809
215 76112067921
216 82331758467
217 88965173634
218 96128879235
219 103943769215
220 112369891568
221 121358179098
222 131045452705
223 141598364657
224 152984814183
225 165134591314
226 178205888487
227 192424050225
228 207773217214
229 224157607451
230 241757235681
231 260871815373
232 281513751347
233 303557354654
234 327204013758
235 352846623591
236 380542604521
237 410132641779
238 441837882417
239 476166763166
240 513244568501
241 552875991626
242 595298911785
243 641163639830
244 690693923568
245 743658547960
246 800307449259
247 861463556653
248 927489454896
249 998122033759
250 1073616831589
251 1155004993368
252 1242840503363
253 1336838364122
254 1437251463710
255 1545360072709
256 1661977234233
257 1786814776569
258 1920113139088
259 2063448404197
260 2217978868489
261 2383444231416
262 2560061714271
263 2749756192388
264 2954140029384
265 3173028835112
266 3406606023460
267 3657205102140
268 3927028729605
269 4216039526545
270 4524378542157
271 4854855338735
272 5210432156538
273 5591320452318
274 5997615341140
275 6432678355173
276 6900440257931
277 7401503658506
278 7935923472094
279 8507698921176
280 9121985613791
281 9779972296778
282 10481695008365
283 11231888014031
284 12037244492736
285 12899802242898
286 13819624063320
287 14802290988582
288 15856413461574
289 16985227999279
290 18188906207573
291 19474005910378
292 20851513866852
293 22326325026173
294 23898854501482
295 25576791032945
296 27374050687677
297 29297785085825
298 31348861995020
299 33536287569513
300 35877571373878
301 38382893355453
302 41053886142950
303 43901104081968
304 46946446141883
305 50204108051685
306 53676940046361
307 57377336350939
308 61332537595488
309 65562010071802
310 70070463258296
311 74872507183403
312 80001862448840
313 85484850303676
314 91328932228621
315 97551426136753
316 104193893216110
317 111291499032207
318 118855680107136
319 126907114190157
320 135496830427865
321 144671323820064
322 154447659718510
323 164850746280523
324 175943029865789
325 187785425297494
326 200402837678017
327 213825573583935
328 228129836387686
329 243394788207229
330 259656100555880
331 276951048128898
332 295372408001308
333 315022312949224
334 335951041002441
335 358204943879364
336 381896774797958
337 407157447700988
338 434056846594499
339 462653227672201
340 493083446736358
341 525514327185379
342 560041822045934
343 596739871210926
344 635774459235221
345 677357043345753
346 721617947916615
347 768651828070267
348 818659947382071
349 871909053778639
350 928574446635731
351 988778166234753
352 1052764315871039
353 1120867930841425
354 1193322757817901
355 1270287022956950
356 1352057006664443
357 1439051862122807
358 1531580818675844
359 1629849845948301
360 1734218983203431
361 1845210766471543
362 1963231355173387
363 2088549568154505
364 2221603627232285
365 2363042882262847
366 2513397317643442
367 2673018252680930
368 2842440119130056
369 3022467570895733
370 3213788021534681
371 3416860738287982
372 3632338964401619
373 3861217299985066
374 4104382436368502
375 4362434396971748
376 4636173645242388
377 4926826861411680
378 5235531974146508
379 5563071881062451
380 5910430046225032
381 6279116501127120
382 6670584749500050
383 7085854413266987
384 7526137088602802
385 7993288591679200
386 8489157470158453
387 9015068652688012
388 9572518850137333
389 10163785754261511
390 10791210897711067
391 11456511538962687
392 12161541485565612
393 12909093132769695
394 13702121465935749
395 14542846107768519
396 15433568900961865
397 16377710312806447
398 17378986695241939
399 18440258704018964
400 19564391071529705
401 20755570949582411
402 22018457386439047
403 23356726275904402
404 24773950214351296
405 26275252712077811
406 27866457504439081
407 29552273922464694
408 31337165259539848
409 33227399320349660
410 35230235974503675
411 37351690528584818
412 39597347299936155
413 41974873496591924
414 44493296706380179
415 47160277725329672
416 49982811681874436
417 52970278499581523
418 56133878179282061
419 59483338907032649
420 63027430702247663
421 66777631366546913
422 70747806885601088
423 74950275897158324
424 79396040028248264
425 84099148852740373
426 89076735956276691
427 94344357494046931
428 99915818699210898
429 105808324410705733
430 112043008781487360
431 118639464322251531
432 125615015050047618
433 132990739940578892
434 140792666389820245
435 149045407596181422
436 157770699026928342
437 166994379865992834
438 176748457644875235
439 187063776998341980
440 197967597115698137
441 209491609907682982
442 221675126156632629
443 234556708720542232
444 248170524008253257
445 262555463978398790
446 277759753148154257
447 293831495559829729
448 310813482728023525
449 328753468305446535
450 347710550679763206
451 367744607047672828
452 388909183481232061
453 411262944482265650
454 434878247952326088
455 459829473396737942
456 486183556622515532
457 514012599533145146
458 543405123083480712
459 574453342123720432
460 607240837832743017
461 641856263739384546
462 678407837811660723
463 717009676228582440
464 757766021256148672
465 800785915078510281
466 846201574090503497
467 894153970799249265
468 944772954057239352
469 998192679940957467
470 1054574598998999002
471 1114092572745729193
472 1176908137941498244
473 1243186380220156068
474 1313124357452072517
475 1386936158523776546
476 1464822475137985052
477 1546986475519904152
478 1633668582687592164
479 1725132032434642630
480 1821625826923504913
481 1923400008591911764
482 2030747808856669021
483 2143992443893454748
484 2263442436828118566
485 2389405501516161851
486 2522239172231657927
487 2662339794827762662
488 2810089122140279928
489 2965865788888901238
490 3130105622518122804
491 3303294048912220655
492 3485902793256661935
493 3678397655822880721
494 3881309783656597107
495 4095233019843644686
496 4320749485246633805
497 4558432045052963694
498 4808927884541195146
499 5072962694935846837
500 5351253877233957048
501 5644505715565496816
502 5953506640570503542
503 6279142569337041938
504 6622296469636957985
505 6983833822758501182
506 7364714966214218441
507 7766020396503560319
508 8188835470993663984
509 8634223244354105956
510 9103353247739606988
511 9597542127490598621
512 10118122355232620060
513 10666398953063649418
514 11243795976246359566
515 11851916504656963858
516 12492394394406242034
517 13166830762643647376
518 13876959280113049276
519 14624730260917768800
520 15412144738756827118
521 16241165858560559675
522 17113903836310379859
523 18032729711603814617
524 19000091389094291588
525 20018394278211394646
526 21090206419904890176
527 22218408379549674586
528 23405991383379214394
529 24655900657922855840
530 25971260733054920447
531 27355568962554142955
532 28812476533873664086
533 30345586986375232663
534 31958701050122348917
535 33656062388418908046
536 35442123098862755421
537 37321288837454494271
538 39298181712054182279
539 41377948043480041326
540 43566011042462824077
541 45867752842187733582
542 48288792899443645139
543 50835368862985547313
544 53514080445496586069
545 56331497481378014280
546 59294449958312362049
547 62410494454177269434
548 65687654871108151351
549 69133944405010650078
550 72757661692258446449
551 76567956714895437881
552 80574576076363198226
553 84787285517436993930
554 89216164669309810650
555 93872287810476624183
556 98767483797004102627
557 103913644517396410612
558 109323008342313317122
559 115008972617188590304
560 120985881276079484821
561 127268203435760345099
562 133870792767367698044
563 140809850089554497126
564 148102755161453197503
565 155767098525603270870
566 163820900637637844942
567 172283744338147865901
568 181176671410187987397
569 190521049856064745518
570 200338732643929667371
571 210653381123030818723
572 221490451722609352913
573 232875880168974285540
574 244836155076064279858
575 257399854454618350729
576 270597753505209134363
577 284461306946947188595
578 299022607324387196393
579 314316157556494936522
580 330379137223720872981
581 347249664306053596923
582 364966601932480944228
583 383571590311851028394
584 403109516322188632580
585 423626536684894067531
586 445169689878000707318
587 467789210658634856350
588 491539256223491906615
589 516475674345602050999
590 542655369245268164786
591 570138921099398175278
592 598991631646445820759
593 629281023280180330441
594 661075898765175536611
595 694449286452087966521
596 729479879036995530536
597 766249253274746559246
598 804840553491947374684
599 845341780479874317892
600 887847709270532363390
601 932456824269900538087
602 979269545527264886050
603 1028391875217283658738
604 1079937893837785146876
605 1134026412482229509140
606 1190778648755994508487
607 1250322239108870187139
608 1312794427854570380431
609 1378338447360063692770
610 1447100537368231488903
611 1519234323886353443245
612 1594904831918341891685
613 1674284615955604703548
614 1757550002315104039501
615 1844885825471350702189
616 1936490413399945501314
617 2032571505375357113308
618 2133341581848380792950
619 2239022936628523727001
620 2349853803251106234173
621 2466084115247580847696
622 2587969772202188814594
623 2715778010601957708960
624 2849794860610791002790
625 2990320826268612801623
626 3137663919881312604841
627 3292145275163357537187
628 3454108146134290880624
629 3623913611784985627414
630 3801932194141041997631
631 3988549633986126939976
632 4184177667134658667538
633 4389249890711481475400
634 4604211763450732517033
635 4829526436216632369725
636 5065687565425830126839
637 5313215517033651573221
638 5572645531360267655772
639 5844533467182978551332
640 6129470937274701558680
641 6428082072368945567599
642 6741009617642953275509
643 7068920409661596870385
644 7412523144457711143763
645 7772565978135991666906
646 8149820308838959505119
647 8545085759558583246946
648 8959210914387900139688
649 9393092096081905484942
650 9847654576812390924313
651 10323856786079873482858
652 10822714375058383258738
653 11345300585504363033599
654 11892724625999843809225
655 12466134762123732166975
656 13066746091384019049071
657 13695843003580534995594
658 14354754457906719294326
659 15044855541399043949228
660 15767599356818453598938
661 16524522173234787263373
662 17317215344939389813582
663 18147324843218670674824
664 19016587675526654645479
665 19926840438043931079016
666 20879987631788730002054
667 21877998581224426939139
668 22922948813750747943564
669 24017032854736515323583
670 25162528721798125724032
671 26361791540983109446290
672 27617300319343170470113
673 28931675968933898248195
674 30307641799646427988543
675 31748013029141042523060
676 33255749376117780597170
677 34833979464535987614907
678 36485957191773883309514
679 38215046201690449866890
680 40024778709942495471787
681 41918887624729511141992
682 43901258744055661679844
683 45975909122042520928839
684 48147052507686152074122
685 50419140725288768710731
686 52796811756407390856279
687 55284860777848805038511
688 57888312548689599342525
689 60612473823674622660105
690 63462877506879557980823
691 66445244976049349832131
692 69565565686206062714235
693 72830162644044961530189
694 76245632986928507058878
695 79818800033156192490453
696 83556800280341432108353
697 87467164249450605987486
698 91557754050760339250568
699 95836703414569266390110
700 100312512144590443101674
701 104994144947796850661754
702 109890966805525852085126
703 115012669046003848628598
704 120369371162690998723736
705 125971740581300260711725
706 131830926967352678705130
707 137958472203409620087177
708 144366419294590767839194
709 151067456387475478961657
710 158074851524126262138873
711 165402344186780012479749
712 173064260782166094009007
713 181075686618515158669401
714 189452403070483591658963
715 198210758157045276851990
716 207367787816863755537554
717 216941419968853509884406
718 226950416593827686309789
719 237414220623598727084846
720 248353081885212669271497
721 259788297816342843287024
722 271742163610371802612441
723 284237792523982010867070
724 297299244971900316832754
725 310951810939034409539448
726 325221972089947884755552
727 340137192458092120470826
728 355726048707924046293860
729 372018559778437564163722
730 389046165740879899391796
731 406841485727008095159917
732 425438446834952061482969
733 444872667049961813016619
734 465181456662524208324350
735 486403540239914243002621
736 508579181028865908732801
737 531750623724110311436263
738 555962125451142487259110
739 581259638602094308874188
740 607690926875179086820771
741 635306074993781462159931
742 664157557633994360254684
743 694299880053050612124369
744 725789681096027209174405
745 758686317500224675119003
746 793051980728950481256112
747 828951292542859193848052
748 866451389392594666728500
749 905622589465667636041283
750 946538569198260433572086
751 989275911305709195482576
752 1033914163960688367602168
753 1080536599241625029540526
754 1129230463158787117584411
755 1180086474203699116739039
756 1233198849582624548563547
757 1288666164193600302095893
758 1346591690348797638256539
759 1407082845663516238115632
760 1470251177372541107596214
761 1536213331381813562938327
762 1605091500524882454307209
763 1677012821636362803708277
764 1752109307625251346332525
765 1830518936499416105446463
766 1912386229990529946174818
767 1997861600997905826216710
768 2087101221632389921894880
769 2180268242377123476983599
770 2277533526285063806430647
771 2379074949698531106481851
772 2485077192918403240503801
773 2595733099820296167831699
774 2711244596605689844034887
775 2831821950871175900046942
776 2957683469914148469125237
777 3089057011144357134326459
778 3226181118589406642563943
779 3369304248086730659204016
780 3518684356529077654174184
781 3674590573269403664816524
782 3837304592281188034946587
783 4007119874568243489468150
784 4184341109909215970953407
785 4369286059118571475674333
786 4562287244980142058544570
787 4763691147020503127872828
788 4973857515569199966256057
789 5193161394177388658571628
790 5421995158218771252943311
791 5660767722071156698807289
792 5909903683617470719325536
793 6169845535301669075110142
794 6441056105665103306746858
795 6724017804863539513276908
796 7019231576156230568151539
797 7327219302959742311424656
798 7648526715600816478229980
799 7983722708115511989653793
800 8333398071889080148971703
801 8698168104615187564776324
802 9078676052239906611061190
803 9475592538317979574116279
804 9889614053873589695870466
805 10321465772348057046794661
806 10771905605125192019066695
807 11241723794550386307975885
808 11731741133402949118347416
809 12242811987683888909957425
810 12775829053291864656149646
811 13331723175360609696088623
812 13911461270615188121934951
813 14516049557179982485309753
814 15146539109957804605816410
815 15804025982452376502606968
816 16489648805902504878236397
817 17204592222150686633259339
818 17950093346105909301277724
819 18727442281960890420785896
820 19537979374574589510568894
821 20383098837812993632711149
822 21264256244188272068278105
823 22182969545656229025542008
824 23140815955505250959508137
825 24139435760452207789397478
826 25180540970185629007489065
827 26265916974071879301081299
828 27397419036112140984654396
829 28576976274451356273288828
830 29806601617148913715589657
831 31088394250503527597997246
832 32424535715819098138205138
833 33817294034885164753573534
834 35269035132892741209195342
835 36782226262118776943957628
836 38359431697720179752638879
837 40003316982216310071268440
838 41716661992097679352584241
839 43502365552745704949532767
840 45363440741748034612333241
841 47303019219533712000738780
842 49324366132927065494824752
843 51430886173919130072130264
844 53626118513646007797525502
845 55913741180210394796464589
846 58297588010253079940242767
847 60781656446092432853995831
848 63370102142204928797795371
849 66067243345075329702224492
850 68877580122838993936745347
851 71805804242975014339302437
852 74856793516656047549178016
853 78035616129424813698758431
854 81347552399153959247812527
855 84798107130587936605185792
856 88393003792192053878626956
857 92138188740847868724290177
858 96039855779846099777212681
859 100104461447860288686228832
860 104338719158965305283233506
861 108749603259758128220542810
862 113344376681920657669005198
863 118130609692485907584146254
864 123116174171713668706644562
865 128309247437559943151590524
866 133718343311618733703590296
867 139352334935700397071880392
868 145220449415623539628643412
869 151332271346384877841587318
870 157697777636138782349932898
871 164327365082126804363681995
872 171231845672746709190353734
873 178422449747872615075724831
874 185910864953122706870876810
875 193709269367134792693201060
876 201830327831307283169717661
877 210287194684421721200879595
878 219093557248996694457349699
879 228263675412979184150786620
880 237812379448373070448522507
881 247755072268766057150039432
882 258107777881349648639513046
883 268887188450590574857813123
884 280110664175909376764661405
885 291796235036300594744150132
886 303962654675975035762674147
887 316629456116921307265352203
888 329816954394528951166704952
889 343546247776892439028363882
890 357839277589467068572874390
891 372718893899205298227086552
892 388208861758552781125776451
893 404333861920258484802169112
894 421119557147524027093458639
895 438592669366344347159638371
896 456780990546059403076546853
897 475713382975963466440364044
898 495419852652926525586060259
899 515931639592609025330426161
900 537281234582595255971775495
901 559502379147671228890355035
902 582630146657763680331401660
903 606701047704967057080707704
904 631753054207588509095772945
905 657825599270043591012809464
906 684959666711397879108573734
907 713197913656009536791020005
908 742584703748515460213721897
909 773166107215890177071430795
910 804989999582393090388980778
911 838106203889728697555741041
912 872566535109664101788883776
913 908424800844632050443438459
914 945736910070355823907719155
915 984561037699705341672423801
916 1024957682657527998335105937
917 1066989669817793881656371673
918 1110722269702906263378474391
919 1156223388437181822268234450
920 1203563642384657755659071406
921 1252816362121660243992972091
922 1304057724124661610958578983
923 1357366969528239444507922086
924 1412826498729032764519384827
925 1470521878440330562505000281
926 1530541986521798317901219447
927 1592979263367046549097530604
928 1657929830454472910447482751
929 1725493501833824224156038867
930 1795773943395443027431884588
931 1868878961168918652172477234
932 1944920648464298939850324412
933 2024015403509805987620452215
934 2106284104630618833411966065
935 2191852440247840989671711695
936 2280851090012757968076570705
937 2373415750761838485415538326
938 2469687329281727982916856425
939 2569812319363035718014881628
940 2673943023198597924067988665
941 2782237588360282621843664659
942 2894860220075360385724801079
943 3011981611319344338975300808
944 3133779211740787927547653013
945 3260437279010059231732259792
946 3392147112831636704040105906
947 3529107544762388162241327939
948 3671525263056218075202846309
949 3819614882506123610973463728
950 3973599202778076349242182544
951 4133709765424844302155718817
952 4300187244331686445669076916
953 4473281539090628242642457465
954 4653252060677376055690045136
955 4840368364006596268551640110
956 5034910615124903670777233178
957 5237169714244498051214432579
958 5447447612310415713260105722
959 5666058028423232207841754502
960 5893327006590335952209638305
961 6129593075832491029022396147
962 6375207601822935196254081342
963 6630535599601822099183066642
964 6895956394586511345193980598
965 7171863828680926946962935251
966 7458666651932195117180016182
967 7756789442194076877028995563
968 8066673387240159584620159601
969 8388776547588285036817810989
970 8723574294040124061588040883
971 9071560347337280969412759571
972 9433247700649776766464441780
973 9809168951917710961886594529
974 10199876794244479430474087688
975 10605945190151142210414271704
976 11027970456462355822028529959
977 11466571681412043856991985135
978 11922391276187240592663812818
979 12396096300149291458040456898
980 12888379733250823124846647604
981 13399960996005387597007825094
982 13931586572067629152739676238
983 14484031502783744181640683846
984 15058100875791658829567108879
985 15654630469277729345791433952
986 16274487457378626934113354428
987 16918572094682978369057834395
988 17587819453643898935581740110
989 18283200218408700953062092781
990 19005721487095279724086127778
991 19756428669432534221445600965
992 20536407510107561162538789378
993 21346785061936345585799590764
994 22188730601768641280947545840
995 23063457767373945651290509089
996 23972226908920207177069799083
997 24916346276444874339829223829
998 25897173069354277097301608815
999 26916115841989822703521542283
1000 27974637231164655184460858243