0 1
1 1
2 1
3 2
4 3
5 3
6 5
7 6
8 8
9 10
10 13
11 16
12 21
13 25
14 31
15 38
16 47
17 56
18 69
19 82
20 99
21 118
22 141
23 166
24 199
25 233
26 275
27 322
28 379
29 440
30 516
31 598
32 696
33 805
34 933
35 1074
36 1242
37 1425
38 1639
39 1878
40 2154
41 2458
42 2812
43 3202
44 3650
45 4148
46 4716
47 5344
48 6064
49 6857
50 7758
51 8758
52 9888
53 11136
54 12549
55 14108
56 15863
57 17804
58 19981
59 22384
60 25081
61 28051
62 31371
63 35036
64 39121
65 43619
66 48633
67 54148
68 60277
69 67023
70 74504
71 82726
72 91840
73 101844
74 112908
75 125058
76 138472
77 153180
78 169410
79 187190
80 206774
81 228226
82 251819
83 277636
84 306013
85 337033
86 371079
87 408290
88 449081
89 493617
90 542406
91 595634
92 653872
93 717383
94 786800
95 862438
96 945056
97 1035007
98 1133156
99 1239974
100 1356419
101 1483047
102 1620999
103 1770914
104 1934087
105 2111324
106 2304077
107 2513298
108 2740696
109 2987359
110 3255236
111 3545672
112 3860854
113 4202353
114 4572731
115 4973798
116 5408469
117 5878924
118 6388457
119 6939612
120 7536214
121 8181183
122 8878880
123 9632788
124 10447832
125 11328046
126 12279135
127 13305734
128 14414337
129 15610399
130 16901274
131 18293270
132 19794856
133 21413261
134 23158128
135 25037906
136 27063513
137 29244669
138 31593917
139 34122390
140 36844344
141 39772691
142 42923584
143 46311852
144 49955977
145 53872893
146 58083603
147 62607656
148 67468829
149 72689489
150 78296784
151 84316226
152 90778609
153 97713239
154 105154973
155 113137268
156 121699808
157 130880663
158 140724812
159 151275832
160 162584579
161 174700665
162 187681872
163 201584570
164 216474144
165 232414883
166 249480665
167 267744536
168 287290248
169 308200615
170 330570302
171 354493510
172 380077061
173 407427741
174 436666436
175 467914018
176 501306920
177 536982247
178 575093809
179 615796742
180 659264764
181 705673149
182 755217715
183 808096840
184 864530992
185 924744191
186 988985049
187 1057506266
188 1130587683
189 1208514669
190 1291601938
191 1380171208
192 1474576767
193 1575180914
194 1682381932
195 1796588188
196 1918247027
197 2047818024
198 2185804044
199 2332721860
200 2489136011
201 2655627891
202 2832830836
203 3021398150
204 3222040693
205 3435491948
206 3662548976
207 3904035614
208 4160844943
209 4433901255
210 4724205585
211 5032794220
212 5360788128
213 5709349375
214 6079732499
215 6473239416
216 6891274392
217 7335295041
218 7806871987
219 8307637352
220 8839346797
221 9403826299
222 10003038556
223 10639025262
224 11313978951
225 12030182462
226 12790083847
227 13596233756
228 14451365488
229 15358327324
230 16320169118
231 17340071332
232 18421435335
233 19567810147
234 20782988957
235 22070930088
236 23435861168
237 24882196429
238 26414645600
239 28038128472
240 29757891170
241 31579414314
242 33508538443
243 35551367984
244 37714402403
245 40004437208
246 42428704043
247 44994764438
248 47710660694
249 50584805021
250 53626137652
251 56844012602
252 60248366379
253 63849595838
254 67658739812
255 71687351808
256 75947690464
257 80452588652
258 85215656834
259 90251143342
260 95574153024
261 101200502056
262 107146947618
263 113431038794
264 120071361615
265 127087380528
266 134499701837
267 142329909212
268 150600840669
269 159336420144
270 168561953170
271 178303948234
272 188590434320
273 199450776246
274 210916009060
275 223018649410
276 235793052395
277 249275212304
278 263503145897
279 278516686960
280 294357890312
281 311070822860
282 328701994959
283 347300140462
284 366916679651
285 387605493608
286 409423412996
287 432429989476
288 456688017567
289 482263295267
290 509225184214
291 537646365270
292 567603430501
293 599176637294
294 632450540736
295 667513737430
296 704459544031
297 743385737628
298 784395273980
299 827596028270
300 873101562466
301 921030857364
302 971509136111
303 1024667595068
304 1080644276360
305 1139583802414
306 1201638308816
307 1266967172420
308 1335738012341
309 1408126420664
310 1484317024649
311 1564503225446
312 1648888333961
313 1737685307349
314 1831117968192
315 1929420748754
316 2032839986064
317 2141633680800
318 2256072883188
319 2376441455344
320 2503037558866
321 2636173432785
322 2776176975920
323 2923391548244
324 3078177664757
325 3240912809215
326 3411993252985
327 3591833894738
328 3780870197247
329 3979558062980
330 4188375908864
331 4407824566180
332 4638429508664
333 4880740793269
334 5135335435691
335 5402817403532
336 5683820162144
337 5979006709157
338 6289072309684
339 6614744591196
340 6956786462602
341 7315996284263
342 7693210998393
343 8089306363182
344 8505200316664
345 8941853298119
346 9400271842201
347 9881509005042
348 10386668220373
349 10916903820933
350 11473425183944
351 12057497374894
352 12670445580728
353 13313655898275
354 13988580093408
355 14696736525802
356 15439715266499
357 16219179192121
358 17036869463139
359 17894606814344
360 18794297438562
361 19737934468455
362 20727604305728
363 21765488333580
364 22853869697286
365 23995135281341
366 25191782995819
367 26446424016296
368 27761790623935
369 29140738756641
370 30586256415434
371 32101466568460
372 33689636187877
373 35354179511057
374 37098667767428
375 38926832854932
376 40842577776447
377 42849980784233
378 44953306604285
379 47157011059592
380 49465753154232
381 51884400247465
382 54418041028204
383 57071991304926
384 59851807964192
385 62763295397966
386 65812520535449
387 69005819995026
388 72349816232507
389 75851425499924
390 79517875224832
391 83356712809914
392 87375824351888
393 91583444390305
394 95988176027389
395 100599001727850
396 105425304978048
397 110476882188964
398 115763966029756
399 121297238566298
400 127087856351494
401 133147464928204
402 139488225846201
403 146122832603186
404 153064539753752
405 160327180453286
406 167925197770922
407 175873663996246
408 184188314362768
409 192885568221408
410 201982565380124
411 211497189346942
412 221448106432480
413 231854791264266
414 242737568906507
415 254117642785968
416 266017140082121
417 278459142316982
418 291467734209586
419 305068037181026
420 319286261983946
421 334149745312433
422 349687006521291
423 365927787652514
424 382903114494768
425 400645340342460
426 419188211779156
427 438566916418498
428 458818153799947
429 479980187500000
430 502092921465234
431 525197956887820
432 549338674446385
433 574560296274195
434 600909974590815
435 628436859243674
436 657192193146040
437 687229385886270
438 718604116553789
439 751374413840830
440 785600766853354
441 821346212304346
442 858676453842028
443 897659956950930
444 938368077512848
445 980875164965655
446 1025258700839190
447 1071599410914030
448 1119981414407520
449 1170492345903941
450 1223223516075616
451 1278270044088286
452 1335731030775102
453 1395709702441391
454 1458313597349203
455 1523654721882152
456 1591849751431145
457 1663020199819611
458 1737292635730460
459 1814798866537384
460 1895676171354033
461 1980067500471711
462 2068121726379676
463 2159993859951502
464 2255845320847006
465 2355844171872027
466 2460165410125903
467 2568991221027612
468 2682511291872699
469 2800923086974457
470 2924432185380116
471 3053252578893258
472 3187607035659840
473 3327727422932699
474 3473855098584975
475 3626241260442638
476 3785147367889845
477 3950845519962653
478 4123618909192896
479 4303762230774606
480 4491582171184740
481 4687397850722818
482 4891541349590229
483 5104358186519702
484 5326207884994653
485 5557464490843046
486 5798517181734054
487 6049770826620380
488 6311646641827136
489 6584582795711267
490 6869035114692348
491 7165477736694458
492 7474403870988120
493 7796326504028610
494 8131779217210501
495 8481316949270300
496 8845516876124080
497 9224979234258302
498 9620328267428037
499 10032213115547560
500 10461308833313786
501 10908317349756750
502 11373968563978439
503 11859021380840690
504 12364264889708208
505 12890519481901708
506 13438638118702740
507 14009507536948052
508 14604049612738253
509 15223222661955912
510 15868022906940847
511 16539485878931992
512 17238687995427000
513 17966748072428229
514 18724829020478496
515 19514139475093834
516 20335935620419960
517 21191522946550841
518 22082258210326496
519 23009551329260692
520 23974867489372460
521 24979729186081888
522 26025718490092463
523 27114479246040118
524 28247719508153395
525 29427213908651866
526 30654806275422132
527 31932412182945266
528 33262021765541794
529 34645702464187667
530 36085602049771424
531 37583951580578146
532 39143068650669397
533 40765360573796015
534 42453327873572025
535 44209567710331776
536 46036777630863408
537 47937759256412159
538 49915422310619328
539 51972788588081002
540 54112996280975064
541 56339304248574941
542 58655096664409595
543 61063887609120848
544 63569326061127233
545 66175200836715220
546 68885445949365849
547 71704145922233092
548 74635541542963229
549 77684035576085551
550 80854198941603310
551 84150776856665318
552 87578695468797321
553 91143068457842635
554 94849204156771569
555 98702612647691872
556 102709013405001149
557 106874342921547603
558 111204762911985292
559 115706668507204694
560 120386697058282747
561 125251736940667358
562 130308937001428139
563 135565716017470460
564 141029772832473696
565 146709096515985916
566 152611977239557248
567 158747017187573064
568 165123142224978344
569 171749613614145094
570 178636040530993306
571 185792392645400068
572 193229013546335107
573 200956634248123126
574 208986387588828907
575 217329822728884684
576 225998920592223911
577 235006109427799375
578 244364281367644047
579 254086809127546594
580 264187563760699432
581 274680932578951889
582 285581838187024084
583 296905757710727196
584 308668743202428769
585 320887442269524528
586 333579119947406236
587 346761680827754202
588 360453692502820962
589 374674409299275475
590 389443797404597954
591 404782560320467046
592 420712165788917936
593 437254873086949315
594 454433761879187425
595 472272761482975670
596 490796681782787427
597 510031244604994289
598 530003116837729909
599 550739944063888502
600 572270386041042697
601 594624152750573741
602 617832042402616528
603 641925980071142194
604 666939058399279813
605 692905579001581401
606 719861096058184815
607 747842460676951244
608 776887867577536439
609 807036902620435274
610 838330592794764361
611 870811457135112940
612 904523560242587248
613 939512566824421190
614 975825798993171525
615 1013512294681273492
616 1052622868978839584
617 1093210176692212351
618 1135328777999772852
619 1179035205440707798
620 1224388034186842886
621 1271447953768586224
622 1320277843279826680
623 1370942848168476168
624 1423510460714248872
625 1478050602232191827
626 1534635709185760849
627 1593340821176664054
628 1654243673078824688
629 1717424789212701310
630 1782967581913142240
631 1850958452311874448
632 1921486895779629800
633 1994645609770512044
634 2070530606607007017
635 2149241328870018922
636 2230880770028331635
637 2315555597889184661
638 2403376283606930927
639 2494457233745112716
640 2588916928233357432
641 2686878061628360635
642 2788467690627720380
643 2893817385154973196
644 3003063386079196088
645 3116346766792673915
646 3233813601826758112
647 3355615139634814872
648 3481907982842501280
649 3612854272994459673
650 3748621883225717184
651 3889384615782805092
652 4035322407953475144
653 4186621543226220121
654 4343474871372847728
655 4506082034165879976
656 4674649700567152922
657 4849391807985379347
658 5030529813585113456
659 5218292952131111884
660 5412918504500916529
661 5614652073229863626
662 5823747869381341017
663 6040469006981770550
664 6265087809476572785
665 6497886124322137932
666 6739155650338382866
667 6989198273805978828
668 7248326418111768520
669 7516863402790249944
670 7795143816947551472
671 8083513902779837040
672 8382331954361051063
673 8691968727269093935
674 9012807864425500432
675 9345246333569206412
676 9689694881944267184
677 10046578503473938105
678 10416336924212091380
679 10799425101188798142
680 11196313740665078728
681 11607489830752071930
682 12033457194638984451
683 12474737059223857072
684 12931868645628082528
685 13405409776219646009
686 13895937504876840653
687 14404048764941964046
688 14930361041853769401
689 15475513064733192797
690 16040165524176332968
691 16625001810345860320
692 17230728778895815718
693 17858077538630902551
694 18507804268723358485
695 19180691059199013786
696 19877546782813097257
697 20599207991829093617
698 21346539848136133222
699 22120437080012800348
700 22921824974296053770
701 23751660397058515279
702 24610932851886645874
703 25500665568649134618
704 26421916632201215889
705 27375780143692904702
706 28363387424289613248
707 29385908253752788758
708 30444552154063921707
709 31540569710309509033
710 32675253939406671793
711 33849941698649226728
712 35066015145061333776
713 36324903237302075984
714 37628083291529321322
715 38977082582719637092
716 40373480003297728232
717 41818907770317652608
718 43315053193507165359
719 44863660495164640658
720 46466532694693603192
721 48125533548501065745
722 49842589558544934108
723 51619692039985292134
724 53458899261739836754
725 55362338650129180155
726 57332209069945305719
727 59370783172849040258
728 61480409827992480112
729 63663516624484218493
730 65922612461172999498
731 68260290213082558812
732 70679229490573591080
733 73182199480269644572
734 75772061884456225392
735 78451773947685807272
736 81224391587951106864
737 84093072620859049258
738 87061080094844420332
739 90131785725544414492
740 93308673448086677774
741 96595343075092961370
742 99995514079887348016
743 103513029492396952030
744 107151859927997439639
745 110916107736466314860
746 114810011292101040743
747 118837949411832481258
748 123004445923221824680
749 127314174368845299268
750 131771962869816853130
751 136382799134616525780
752 141151835636883095120
753 146084394947995378455
754 151185975249039620444
755 156462256007651925780
756 161919103845307538984
757 167562578580200813923
758 173398939472314113002
759 179434651655468543726
760 185676392784016478093
761 192131059878627906107
762 198805776399932992691
763 205707899534123310356
764 212845027720435168720
765 220225008404263572925
766 227855946047032041468
767 235746210376225472214
768 243904444907959948047
769 252339575725148120661
770 261060820544948734094
771 270077698058207845208
772 279400037575942213451
773 289037988965237164494
774 299002032911025125192
775 309302991485776620550
776 319952039065060226038
777 330960713570662760115
778 342340928080771162496
779 354104982788586470600
780 366265577350478299078
781 378835823604726833061
782 391829258703651941780
783 405259858639856180142
784 419142052211135875361
785 433490735404491241921
786 448321286245615679440
787 463649580094000245776
788 479492005431954896480
789 495865480127394842761
790 512787468220688465982
791 530275997215157584334
792 548349675923603704520
793 567027712850198902533
794 586329935162300393329
795 606276808231287676598
796 626889455799251951184
797 648189680750434024111
798 670199986546605993793
799 692943599305101239636
800 716444490581176636608
801 740727400833238737874
802 765817863635205252976
803 791742230614406198790
804 818527697181993185429
805 846202329034151963611
806 874795089493923790489
807 904335867671848286644
808 934855507518185162103
809 966385837744900649956
810 998959702693254578825
811 1032610994125173912742
812 1067374684017486843656
813 1103286858337239964131
814 1140384751880543884484
815 1178706784153274242104
816 1218292596379591405952
817 1259183089616747991996
818 1301420464065847542725
819 1345048259557214306456
820 1390111397303892252261
821 1436656222902206515405
822 1484730550676929836160
823 1534383709350311424280
824 1585666589136743513257
825 1638631690242710691083
826 1693333172878209696488
827 1749826908759772300444
828 1808170534215887963861
829 1868423504875513739878
830 1930647152055315460384
831 1994904740826963670330
832 2061261529885184722233
833 2129784833198647454989
834 2200544083569669951892
835 2273610898085670743622
836 2349059145593906370419
837 2426965016183366411039
838 2507407092811168308023
839 2590466425058415769638
840 2676226605158927651178
841 2764773846287004781589
842 2856197063254019858176
843 2950587955601330279744
844 3048041093245960049707
845 3148654004668058969157
846 3252527267803552649089
847 3359764603632639694972
848 3470472972634877582240
849 3584762674103321816572
850 3702747448496116870676
851 3824544582820023198130
852 3950275019232291573944
853 4080063466857563432794
854 4214038517014636005428
855 4352332761852162835404
856 4495082916596939109106
857 4642429945416488245582
858 4794519191108822933540
859 4951500508623959191310
860 5113528402639758321518
861 5280762169199780065250
862 5453366041645869443219
863 5631509340856569520438
864 5815366630034710352439
865 6005117874058941627572
866 6200948603653738023984
867 6403050084396616229510
868 6611619490828790912499
869 6826860085692344105004
870 7048981404572391598382
871 7278199445971982240710
872 7514736867111106141583
873 7758823185482569408283
874 8010694986469608888687
875 8270596137063461073130
876 8538778005999905191256
877 8815499690358848402024
878 9101028248960854417620
879 9395638942610973563916
880 9699615481539362079230
881 10013250280095857573979
882 10336844719064339859355
883 10670709415661334808340
884 11015164501601881542960
885 11370539909304938400047
886 11737175666639360698137
887 12115422200291161441200
888 12505640648171979375896
889 12908203180958483864987
890 13323493333202515443602
891 13751906344111344201534
892 14193849508458677128466
893 14649742537736184567187
894 15120017932028031774031
895 15605121362729275706684
896 16105512066613606395520
897 16621663251383144815397
898 17154062513229886374032
899 17703212266554227346352
900 18269630186395463859034
901 18853849663733269868069
902 19456420274241663227897
903 20077908260668947776588
904 20718897029453061725056
905 21379987661761338870086
906 22061799439593420547380
907 22764970387152854493856
908 23490157828156955575808
909 24238038959308084862127
910 25009311440628276552448
911 25804694002899219012972
912 26624927072943488930600
913 27470773417009103856396
914 28343018803029035562969
915 29242472682039109341706
916 30169968889563444666410
917 31126366367273678557270
918 32112549905770521101705
919 33129430908818143499784
920 34177948179921400992704
921 35259068731602199211676
922 36373788618308522400925
923 37523133793339963217100
924 38708160990768980217422
925 39929958632770972616735
926 41189647763390496276208
927 42488383009187801699870
928 43827353567843521835562
929 45207784225198818577622
930 46630936401861872780960
931 48098109229893198147288
932 49610640660756497050792
933 51169908605084895888450
934 52777332105507916519673
935 54434372543128784014780
936 56142534878959040841015
937 57903368930942256209442
938 59718470687938639534121
939 61589483661347125691008
940 63518100275804850979304
941 65506063299688204987094
942 67555167316926953513313
943 69667260240906110578446
944 71844244872042379261776
945 74088080499863398810423
946 76400784551255756081760
947 78784434285766904532042
948 81241168539710126314411
949 83773189520017990339560
950 86382764649680976140084
951 89072228465780651288874
952 91843984572046053024791
953 94700507647010539117983
954 97644345509794445574052
955 100678121244662717476562
956 103804535386484602935776
957 107026368168320759048024
958 110346481833371795627985
959 113767823012594428618024
960 117293425170331688285757
961 120926411119348929132536
962 124669995607740395634582
963 128527487979188715967312
964 132502294909166429185107
965 136597923218658001748160
966 140817982768122178704681
967 145166189433374814147756
968 149646368166249615470160
969 154262456141824586475767
970 159018505995216235330016
971 163918689149843388505206
972 168967299240314750890275
973 174168755631962714190235
974 179527607040337593475424
975 185048535252812461869230
976 190736358955781010066888
977 196596037669733804542817
978 202632675795872287548773
979 208851526776688871526934
980 215257997374358652021658
981 221857652069522312863889
982 228656217584501491442304
983 235659587533686244449036
984 242873827205341723754177
985 250305178477742913895938
986 257960064874101157768432
987 265845096759370219877362
988 273967076683623371894128
989 282333004875278524127748
990 290950084889102405719082
991 299825729412470836748686
992 308967566235068145552863
993 318383444385714169858184
994 328081440441766922900576
995 338069865015012922476650
996 348357269419771985920568
997 358952452527364665011870
998 369864467812962420882776
999 381102630599218237377652
1000 392676525503006184199944