0 1
1 1
2 1
3 2
4 2
5 3
6 4
7 6
8 7
9 9
10 12
11 14
12 18
13 22
14 28
15 34
16 41
17 50
18 60
19 72
20 86
21 105
22 124
23 146
24 174
25 204
26 240
27 282
28 332
29 386
30 450
31 524
32 606
33 703
34 812
35 940
36 1082
37 1243
38 1428
39 1636
40 1873
41 2140
42 2448
43 2788
44 3172
45 3610
46 4096
47 4646
48 5264
49 5962
50 6736
51 7606
52 8582
53 9666
54 10884
55 12240
56 13759
57 15444
58 17319
59 19410
60 21730
61 24310
62 27172
63 30360
64 33878
65 37777
66 42104
67 46878
68 52164
69 58006
70 64468
71 71582
72 79436
73 88100
74 97632
75 108144
76 119706
77 132440
78 146424
79 161790
80 178678
81 197206
82 217544
83 239844
84 264316
85 291099
86 320434
87 352568
88 387704
89 426148
90 468180
91 514132
92 564294
93 619078
94 678884
95 744108
96 815267
97 892830
98 977384
99 1069460
100 1169724
101 1278884
102 1397644
103 1526840
104 1667314
105 1820056
106 1985968
107 2166194
108 2361934
109 2574366
110 2804916
111 3055020
112 3326286
113 3620308
114 3938985
115 4284278
116 4658222
117 5063174
118 5501500
119 5975890
120 6489045
121 7044034
122 7644136
123 8292756
124 8993694
125 9750916
126 10568820
127 11451838
128 12405020
129 13433726
130 14543500
131 15740556
132 17031382
133 18423037
134 19922840
135 21538952
136 23279966
137 25154956
138 27173920
139 29347272
140 31686406
141 34203172
142 36910550
143 39822376
144 42953242
145 46319002
146 49936392
147 53823548
148 57999348
149 62484465
150 67300876
151 72471700
152 78022086
153 83978572
154 90369672
155 97225388
156 104578268
157 112462796
158 120915516
159 129975882
160 139685476
161 150089033
162 161233664
163 173170082
164 185952240
165 199637268
166 214286444
167 229964676
168 246741484
169 264690056
170 283889134
171 304422338
172 326378088
173 349851212
174 374942080
175 401757770
176 430411437
177 461024300
178 493724844
179 528649258
180 565943086
181 605760206
182 648264796
183 693630330
184 742041936
185 793696096
186 848800888
187 907577980
188 970262112
189 1037103138
190 1108364916
191 1184328810
192 1265293090
193 1351573296
194 1443505384
195 1541444870
196 1645769328
197 1756877982
198 1875195564
199 2001171748
200 2135282554
201 2278033784
202 2429960224
203 2591629612
204 2763641950
205 2946634258
206 3141281048
207 3348295804
208 3568435277
209 3802499814
210 4051337856
211 4315845476
212 4596973330
213 4895727110
214 5213169692
215 5550427688
216 5908691768
217 6289222444
218 6693351216
219 7122488684
220 7578125718
221 8061837808
222 8575292816
223 9120252104
224 9698579310
225 10312241919
226 10963321566
227 11654017704
228 12386653000
229 13163683388
230 13987701944
231 14861449538
232 15787817948
233 16769864631
234 17810817640
235 18914083390
236 20083261442
237 21322149894
238 22634759480
239 24025320686
240 25498301996
241 27058417634
242 28710640508
243 30460220732
244 32312694282
245 34273903714
246 36350008148
247 38547507212
248 40873254920
249 43334476796
250 45938794592
251 48694241808
252 51609290274
253 54692865544
254 57954380730
255 61403755736
256 65051441482
257 68908455438
258 72986403348
259 77297515088
260 81854670324
261 86671442035
262 91762124768
263 97141771440
264 102826239660
265 108832223808
266 115177306312
267 121879993644
268 128959774516
269 136437163722
270 144333752064
271 152672268988
272 161476632336
273 170772016156
274 180584902952
275 190943165060
276 201876125410
277 213414627458
278 225591123512
279 238439744020
280 251996389899
281 266298811084
282 281386714097
283 297301848434
284 314088107846
285 331791648138
286 350460985796
287 370147127726
288 390903680476
289 412786995516
290 435856295352
291 460173811736
292 485804945942
293 512818412460
294 541286413196
295 571284791674
296 602893234096
297 636195443416
298 671279330868
299 708237238824
300 747166139464
301 788167872208
302 831349364996
303 876822903556
304 924706374240
305 975123533898
306 1028204309880
307 1084085077294
308 1142908987998
309 1204826275592
310 1269994620292
311 1338579491820
312 1410754517522
313 1486701890376
314 1566612759940
315 1650687676536
316 1739137014236
317 1832181471594
318 1930052541612
319 2032993017172
320 2141257552177
321 2255113197542
322 2374840005240
323 2500731619324
324 2633095949696
325 2772255819138
326 2918549662620
327 3072332284498
328 3233975596088
329 3403869443544
330 3582422415776
331 3770062756054
332 3967239257558
333 4174422213196
334 4392104441944
335 4620802308432
336 4861056840170
337 5113434834276
338 5378530098448
339 5656964669506
340 5949390106774
341 6256488890353
342 6578975808160
343 6917599468184
344 7273143818778
345 7646429818010
346 8038317093744
347 8449705710366
348 8881538051920
349 9334800710504
350 9810526540236
351 10309796718984
352 10833742998704
353 11383549971336
354 11960457455180
355 12565763035028
356 13200824636782
357 13867063290540
358 14565965926948
359 15299088418022
360 16068058638456
361 16874579690180
362 17720433335192
363 18607483471924
364 19537679854702
365 20513061888796
366 21535762708102
367 22608013309792
368 23732146914904
369 24910603573182
370 26145934854660
371 27440808861340
372 28798015336490
373 30220471134290
374 31711225804504
375 33273467447468
376 34910528890762
377 36625894019900
378 38423204488904
379 40306266592764
380 42279058607844
381 44345738285412
382 46510650707608
383 48778336574046
384 51153540690478
385 53641220949723
386 56246557570520
387 58974962897488
388 61832091445304
389 64823850434650
390 67956410853492
391 71236218825884
392 74670007627588
393 78264810039896
394 82027971423935
395 85967163172846
396 90090396773200
397 94406038557084
398 98922824914212
399 103649878296806
400 108596723716430
401 113773306177012
402 119190008609316
403 124857670614418
404 130787608123766
405 136991633664876
406 143482077656312
407 150271810411864
408 157374265297983
409 164803462609780
410 172574034529144
411 180701251229196
412 189201047832458
413 198090052717032
414 207385616753952
415 217105844032226
416 227269623604870
417 237896662603778
418 249007520856616
419 260623646700300
420 272767414482876
421 285462163351432
422 298732237973602
423 312603030605456
424 327101024963792
425 342253842077584
426 358090287710056
427 374640401974380
428 391935510719572
429 410008279343142
430 428892768449348
431 448624491894660
432 469240477345890
433 490779328973646
434 513281293009552
435 536788325621496
436 561344163925060
437 586994399515610
438 613786555051940
439 641770164120702
440 670996853996538
441 701520432035340
442 733396975185264
443 766684923568472
444 801445177367824
445 837741197711204
446 875639111851352
447 915207822131588
448 956519119665636
449 999647802201774
450 1044671797153782
451 1091672289054494
452 1140733852255080
453 1191944589118652
454 1245396273257312
455 1301184498901898
456 1359408835728247
457 1420172990361113
458 1483584973782840
459 1549757275479192
460 1618807044731762
461 1690856278616338
462 1766032017835256
463 1844466549769664
464 1926297620180824
465 2011668652611326
466 2100728976562564
467 2193634064978648
468 2290545780457048
469 2391632631601234
470 2497070038911200
471 2607040611714958
472 2721734435252596
473 2841349369198180
474 2966091358121600
475 3096174753424312
476 3231822648418658
477 3373267225791302
478 3520750119314148
479 3674522788916896
480 3834846910465680
481 4001994781009269
482 4176249739087052
483 4357906601871288
484 4547272118516042
485 4744665441907910
486 4950418617750516
487 5164877092710680
488 5388400242605692
489 5621361920101600
490 5864151024141456
491 6117172090550872
492 6380845906186484
493 6655610145704924
494 6941920033032148
495 7240249028551398
496 7551089541704494
497 7874953671646462
498 8212373975274856
499 8563904265566222
500 8930120439385760
501 9311621337022860
502 9709029634910552
503 10122992771397744
504 10554183908457260
505 11003302928927548
506 11471077472770860
507 11958264011384618
508 12465648962843098
509 12994049849937450
510 13544316500842400
511 14117332296013960
512 14714015461146720
513 15335320410040900
514 15982239136747848
515 16655802660486342
516 17357082525403394
517 18087192355461242
518 18847289468776280
519 19638576551241144
520 20462303394206848
521 21319768695886356
522 22212321930393620
523 23141365287264076
524 24108355682166498
525 25114806843665604
526 26162291476440628
527 27252443506689520
528 28386960409435304
529 29567605622712054
530 30796211052262232
531 32074679667654062
532 33404988195895402
533 34789189913518743
534 36229417543639386
535 37727886258424756
536 39286896793063886
537 40908838675454456
538 42596193573427216
539 44351538766869840
540 46177550746069902
541 48077008944354840
542 50052799606214212
543 52107919797930968
544 54245481566346364
545 56468716248541902
546 58780978940926616
547 61185753130232100
548 63686655496194488
549 66287440887642404
550 68992007480893792
551 71804402127610606
552 74728825895667530
553 77769639813649120
554 80931370822766216
555 84218717947556718
556 87636558688609762
557 91189955648280856
558 94884163397939332
559 98724635592137076
560 102717032342666715
561 106867227857436638
562 111181318358307894
563 115665630282834942
564 120326728782873078
565 125171426531218028
566 130206792843730616
567 135440163132236500
568 140879148695530000
569 146531646865752326
570 152405851516703776
571 158510263950460106
572 164853704176437748
573 171445322592385464
574 178294612086426940
575 185411420570245402
576 192805963963884168
577 200488839641858474
578 208471040360843284
579 216763968686142992
580 225379451930082118
581 234329757625836750
582 243627609549643948
583 253286204316899588
584 263319228565506910
585 273740876750854384
586 284565869574597520
587 295809473064671102
588 307487518334741932
589 319616422040868628
590 332213207566721884
591 345295526954651580
592 358881683613303438
593 372990655829779052
594 387642121108409284
595 402856481371418512
596 418654889044969682
597 435059274068338355
598 452092371849846668
599 469777752207687136
600 488139849330050078
601 507203992783884244
602 526996439615883520
603 547544407575560772
604 568876109507472898
605 591020788943832796
606 614008756943939380
607 637871430224332830
608 662641370617698946
609 688352325913463366
610 715039272119537152
611 742738457203321080
612 771487446351858984
613 801325168809455268
614 832291966348011000
615 864429643418044140
616 897781519046548589
617 932392480532740752
618 968309039012416568
619 1005579386943465130
620 1044253457585075302
621 1084382986538953316
622 1126021575414799856
623 1169224757702023160
624 1214050066912194782
625 1260557107080413892
626 1308807625693499252
627 1358865589134032954
628 1410797260726757408
629 1464671281466907748
630 1520558753530857992
631 1578533326652474438
632 1638671287474332308
633 1701051651959804724
634 1765756260977544404
635 1832869879166879304
636 1902480297184137760
637 1974678437455193006
638 2049558463540648048
639 2127217893247471604
640 2207757715598012576
641 2291282511795150452
642 2377900580318132632
643 2467724066276967708
644 2560869095180833574
645 2657455911254328475
646 2757609020468247014
647 2861457338426309520
648 2969134343278909792
649 3080778233833248104
650 3196532093021781096
651 3316544056920291724
652 3440967489486209712
653 3569961163223794166
654 3703689445954185568
655 3842322493904067544
656 3986036451324783964
657 4135013656844723792
658 4289442856793375664
659 4449519425712800424
660 4615445594310873348
661 4787430685082814396
662 4965691355866794808
663 5150451851596483840
664 5341944264507221386
665 5540408803091661204
666 5746094070075079736
667 5959257349726786316
668 6180164904793755832
669 6409092283384887084
670 6646324636135197956
671 6892157043972776208
672 7146894856853500190
673 7410854043804762676
674 7684361554670471747
675 7967755693915709822
676 8261386506900327146
677 8565616179032200152
678 8880819448203159000
679 9207384030961628686
680 9545711062850542092
681 9896215553394451086
682 10259326856187715252
683 10635489154592074598
684 11025161963553046938
685 11428820648041486934
686 11846956958683348656
687 12280079585112430230
688 12728714727647150888
689 13193406687858289368
690 13674718478656141416
691 14173232454532760628
692 14689550962592682256
693 15224297015067467748
694 15778114983984789924
695 16351671318736615220
696 16945655287253709854
697 17560779741567718704
698 18197781908551444680
699 18857424206625660830
700 19540495089295629380
701 20247809916355287342
702 20980211853678196508
703 21738572802481007128
704 22523794359028128422
705 23336808805757110117
706 24178580134809673160
707 25050105105037419648
708 25952414333524455512
709 26886573422766318020
710 27853684124610663956
711 28854885542156905460
712 29891355370832745030
713 30964311179874356916
714 32075011735530216784
715 33224758367288790736
716 34414896378539709548
717 35646816503042599758
718 36921956408688103948
719 38241802250061920928
720 39607890271334298566
721 41021808461110061158
722 42485198260856672808
723 43999756328649759736
724 45567236359948216856
725 47189450967236121002
726 48868273620400195876
727 50605640649736440952
728 52403553313607624304
729 54264079932757418996
730 56189358093433113778
731 58181596921444625758
732 60243079429427981300
733 62376164939629689470
734 64583291584561840780
735 66866978888022016858
736 69229830428969487105
737 71674536590915678040
738 74203877399465503812
739 76820725450815252454
740 79528048934073085434
741 82328914750310419488
742 85226491731426782288
743 88224053961916397104
744 91324984206813005616
745 94532777449084116584
746 97851044539939837804
747 101283515965594697136
748 104834045734086206992
749 108506615385954552404
750 112305338132602289524
751 116234463126378965954
752 120298379866441281932
753 124501622744660372128
754 128848875735949797288
755 133344977237471816136
756 137994925061408830918
757 142803881586026428134
758 147777179070014917838
759 152920325135114264952
760 158239008422293674206
761 163739104426883719532
762 169426681518163627340
763 175308007149183606036
764 181389554262662175998
765 187678007899097066638
766 194180272013277117540
767 200903476505691649288
768 207854984475488070540
769 215042399701774064642
770 222473574360383412944
771 230156616983308066180
772 238099900668358265940
773 246312071546688293264
774 254802057516182251820
775 263579077248898702342
776 272652649480956313080
777 282032602593616539544
778 291729084494449395512
779 301752572807886810636
780 312113885384575232578
781 322824191139369809218
782 333895021228064883020
783 345338280573182434548
784 357166259749592469444
785 369391647240913587024
786 382027542078127672270
787 395087466872008016150
788 408585381251464858800
789 422535695720220288410
790 436953285944523902700
791 451853507485152251030
792 467252210987161283506
793 483165757841446242676
794 499611036332386276040
795 516605478286440606502
796 534167076236959128158
797 552314401120843122188
798 571066620523314566600
799 590443517487364336796
800 610465509905137689585
801 631153670508806515290
802 652529747479190172288
803 674616185690873637068
804 697436148613030753760
805 721013540885914311464
806 745373031593375146696
807 770540078252579635366
808 796540951542494014482
809 823402760793545735992
810 851153480261465954696
811 879821976208905531106
812 909438034819309997134
813 940032390968044939876
814 971636757876737133678
815 1004283857677310505060
816 1038007452913188582016
817 1072842379005884609630
818 1108824577715927225140
819 1145991131628125151372
820 1184380299691836588524
821 1224031553848062721974
822 1264985616775835860344
823 1307284500791572788144
824 1350971547935982274822
825 1396091471284006884840
826 1442690397514557386200
827 1490815910777630815396
828 1540517097897767881500
829 1591844594953654443860
830 1644850635275099129040
831 1699589098899738132896
832 1756115563532939589592
833 1814487357055902938213
834 1874763611627985816448
835 1937005319430938944098
836 2001275390103798213356
837 2067638709918878290738
838 2136162202750706359328
839 2206914892891112140168
840 2279967969765502414222
841 2355394854606668102056
842 2433271269144435428693
843 2513675306370805604040
844 2596687503442277516600
845 2682390916782751182604
846 2770871199452093407116
847 2862216680847641070296
848 2956518448807556403028
849 3053870434187285349458
850 3154369497982062110172
851 3258115521070852714502
852 3365211496659202914590
853 3475763625500548404562
854 3589881413978170788648
855 3707677775132005257534
856 3829269132717328911880
857 3954775528384460464660
858 4084320732071526149172
859 4218032355704906046584
860 4356041970304534761232
861 4498485226594368437304
862 4645501979220860607664
863 4797236414685666405172
864 4953837183101389997410
865 5115457533882726117896
866 5282255455488464654432
867 5454393819332947044274
868 5632040527989360852204
869 5815368667810375113796
870 6004556666095655314974
871 6199788452939037825648
872 6401253627892382375958
873 6609147631586909007184
874 6823671922456670466024
875 7045034158713367995740
876 7273448385725539606060
877 7509135228960025853604
878 7752322092647608979408
879 8003243364339797920812
880 8262140625528378878336
881 8529262868504037119014
882 8804866719635818790464
883 9089216669257928865108
884 9382585308356209564244
885 9685253572251537932752
886 9997510991483517334720
887 10319655950103485610212
888 10651995951591559349448
889 10994847892619040235056
890 11348538344883296145936
891 11713403845249238914862
892 12089791194437566629602
893 12478057764507307944856
894 12878571815387055369708
895 13291712820716250555600
896 13717871803265824651506
897 14157451680214558916118
898 14610867618565994303740
899 15078547400998117492040
900 15560931802446895163900
901 16058474977733089700093
902 16571644860550267257972
903 17100923574141444414728
904 17646807854000488050694
905 18209809482944549446510
906 18790455738912841634800
907 19389289855857750891054
908 20006871498104412614166
909 20643777248565164361912
910 21300601111206808545004
911 21977955028179180147010
912 22676469412025718520300
913 23396793693407810149880
914 24139596884787510483432
915 24905568160525527924528
916 25695417453863884405006
917 26509876071276521630772
918 27349697324683964562112
919 28215657182042878534124
920 29108554936834837181432
921 30029213896994044974840
922 30978482093828683281688
923 31957233011505738499964
924 32966366337685821948272
925 34006808735910163759126
926 35079514640359661560022
927 36185467073622249461852
928 37325678488123466012248
929 38501191631893161112004
930 39713080439359665471080
931 40962450947882839957424
932 42250442240756450569630
933 43578227417431574648869
934 44947014591732718096504
935 46358047918860704182252
936 47812608651998222050995
937 49312016229356241863160
938 50857629392523670981560
939 52450847337005688936288
940 54093110895861825826584
941 55785903757379087277994
942 57530753717742323439292
943 59329233969690493305208
944 61182964428174466671354
945 63093613094061054301442
946 65062897456955977576584
947 67092585938249291411144
948 69184499375516139314392
949 71340512549438131639698
950 73562555754442587965484
951 75852616414289485444696
952 78212740743870964838586
953 80645035458522164028680
954 83151669532179150831006
955 85734876005755370286746
956 88396953847146983157280
957 91140269864316018134074
958 93967260672939715763048
959 96880434720156531639490
960 99882374365980267826224
961 102975738023998353273324
962 106163262363013414602748
963 109447764571334085316278
964 112832144685467588688812
965 116319387985014244144166
966 119912567455614617032960
967 123614846321849669232698
968 127429480652047793524000
969 131359822037004713474316
970 135409320344678568805388
971 139581526552978667874640
972 143880095662823790853742
973 148308789693706793858708
974 152871480764062193726976
975 157572154258797684211208
976 162414912086413552516208
977 167403976028201642757706
978 172543691182083154247704
979 177838529503713848839648
980 183293093447558361260932
981 188912119710707582197222
982 194700483082290371745574
983 200663200401406899763868
984 206805434626592163026122
985 213132499019899786173900
986 219649861448779664302188
987 226363148809010793661504
988 233278151572037878514700
989 240400828460153086822468
990 247737311253055980100040
991 255293909729422311004864
992 263077116747210526121908
993 271093613466535234705400
994 279350274719042419890712
995 287854174527826259453740
996 296612591782038751728966
997 305633016070453885059252
998 314923153678365308364220
999 324490933752314469854034
1000 334344514637267123684798