0 1
1 0
2 1
3 1
4 1
5 2
6 3
7 2
8 5
9 5
10 6
11 9
12 11
13 11
14 18
15 19
16 23
17 31
18 36
19 40
20 56
21 60
22 73
23 92
24 105
25 121
26 155
27 170
28 204
29 247
30 280
31 325
32 397
33 440
34 521
35 615
36 695
37 805
38 954
39 1063
40 1244
41 1442
42 1626
43 1873
44 2176
45 2431
46 2813
47 3221
48 3623
49 4146
50 4751
51 5309
52 6086
53 6905
54 7746
55 8807
56 9992
57 11154
58 12685
59 14290
60 15986
61 18065
62 20342
63 22669
64 25604
65 28681
66 31991
67 35955
68 40248
69 44755
70 50253
71 56029
72 62316
73 69695
74 77641
75 86131
76 96220
77 106855
78 118509
79 131965
80 146418
81 162030
82 180208
83 199438
84 220585
85 244678
86 270531
87 298646
88 330858
89 365049
90 402702
91 445132
92 490665
93 540362
94 596581
95 656433
96 722341
97 795952
98 874981
99 961382
100 1058135
101 1161398
102 1274998
103 1400957
104 1536261
105 1684237
106 1848599
107 2024377
108 2217449
109 2430252
110 2658961
111 2908954
112 3184819
113 3480300
114 3804237
115 4159531
116 4541526
117 4958617
118 5416426
119 5907343
120 6444425
121 7031100
122 7662006
123 8349897
124 9101648
125 9908380
126 10789094
127 11747862
128 12778972
129 13901398
130 15123597
131 16435770
132 17865243
133 19416935
134 21085536
135 22898824
136 24867322
137 26981133
138 29279148
139 31767538
140 34442760
141 37344945
142 40487483
143 43861911
144 47523123
145 51479275
146 55730908
147 60335406
148 65310311
149 70651241
150 76435161
151 82673518
152 89374697
153 96620056
154 104433390
155 112818735
156 121883403
157 131644408
158 142123844
159 153436313
160 165615245
161 178679915
162 192779331
163 207939862
164 224206298
165 241739234
166 260587136
167 280795001
168 302569068
169 325951255
170 351022540
171 378007088
172 406976901
173 438018455
174 471416556
175 507238584
176 545621631
177 586877713
178 631115551
179 678486453
180 729383142
181 783913956
182 842301263
183 904978468
184 972111231
185 1043949833
186 1121035351
187 1203540994
188 1291816566
189 1386463287
190 1487734366
191 1596028482
192 1712090876
193 1836195920
194 1968881361
195 2110980558
196 2262880077
197 2425197939
198 2598960643
199 2784598156
200 2982922370
201 3195087909
202 3421682644
203 3663644952
204 3922389222
205 4198581703
206 4493430462
207 4808535025
208 5144784270
209 5503579931
210 5886871819
211 6295680893
212 6731783234
213 7197394668
214 7693850257
215 8223216375
216 8788182382
217 9390296208
218 10032142730
219 10716791682
220 11446234007
221 12223482591
222 13052248790
223 13934855995
224 14875033841
225 15877035098
226 16943807288
227 18079702930
228 19289845822
229 20577690703
230 21948578873
231 23408401612
232 24961491418
233 26614086412
234 28373262211
235 30244111138
236 32234232731
237 34351786300
238 36603095924
239 38997040907
240 41543392850
241 44249597311
242 47126404565
243 50185110708
244 53434885509
245 56888291629
246 60558821848
247 64457281100
248 68598798416
249 72999003606
250 77671108508
251 82632792122
252 87902678527
253 93496338998
254 99434966311
255 105740169969
256 112430871525
257 119531830958
258 127068739614
259 135063893255
260 143546854007
261 152547470002
262 162092686655
263 172217031031
264 182955914494
265 194341070262
266 206413576400
267 219214613482
268 232782348324
269 247164738028
270 262410541442
271 278564672202
272 295684008070
273 313825289840
274 333042306586
275 353401427920
276 374969709819
277 397810390123
278 422001964087
279 447622497399
280 474747435610
281 503468321814
282 533877248119
283 566062819306
284 600133031011
285 636195116081
286 674354421245
287 714736816131
288 757468583494
289 802673304230
290 850499131352
291 901093108949
292 954601712411
293 1011197501037
294 1071053356168
295 1134340902514
296 1201262826052
297 1272020395774
298 1346816456568
299 1425886919913
300 1509468044947
301 1597797215674
302 1691151001264
303 1789804368779
304 1894037159214
305 2004171044775
306 2120528301431
307 2243436017620
308 2373270637139
309 2510407073446
310 2655229999218
311 2808176920000
312 2969686604974
313 3140208120589
314 3320252625487
315 3510330279852
316 3710968048816
317 3922759546089
318 4146300968865
319 4382206742983
320 4631169348773
321 4893881560223
322 5171062916983
323 5463516969760
324 5772052204217
325 6097506566390
326 6440816081811
327 6802919556004
328 7184796424200
329 7587531975415
330 8012220346459
331 8460000784951
332 8932135772059
333 9429894866117
334 9954607313555
335 10507735729168
336 11090757794147
337 11705217829847
338 12352815035071
339 13035262659079
340 13754359572039
341 14512072723306
342 15310393687910
343 16151409989074
344 17037403902168
345 17970682601620
346 18953673871515
347 19989017435820
348 21079391967780
349 22227611641483
350 23436735719362
351 24709864733442
352 26050266695275
353 27461477074192
354 28947091319637
355 30510893371935
356 32156975919541
357 33889497055382
358 35712844753836
359 37631744844795
360 39651013507187
361 41775725963296
362 44011346844637
363 46363441116842
364 48837886270758
365 51440987075244
366 54179181895364
367 57059261574308
368 60088508755426
369 63274356211009
370 66624658188817
371 70147809997546
372 73852401402803
373 77747497813894
374 81842786645813
375 86148175537788
376 90674136658246
377 95431828251433
378 100432687793566
379 105688790104435
380 111212997861629
381 117018491583261
382 123119203485202
383 129529936955892
384 136265891650283
385 143343116100722
386 150778658279146
387 158590018683880
388 166795693630004
389 175415287183278
390 184468959974461
391 193977997364831
392 203964954446498
393 214453023166614
394 225466708797422
395 237031927100214
396 249175368418283
397 261925206544367
398 275311230707200
399 289364117455583
400 304116268589191
401 319601884189843
402 335856233576418
403 352916534820000
404 370822064036083
405 389613322820817
406 409333071234960
407 430026364777546
408 451739724157093
409 474522221021601
410 498425552203118
411 523503093960771
412 549811169820321
413 577409036515727
414 606357945377129
415 636722476414238
416 668570561987346
417 701972420105975
418 737002104178247
419 773737419349375
420 812258869785070
421 852651290921519
422 895003803306965
423 939408618905258
424 985962928269063
425 1034768724500707
426 1085931633020239
427 1139562900749903
428 1195779256523398
429 1254701586974776
430 1316457226508594
431 1381179661241321
432 1449007241234990
433 1520085595823243
434 1594567371974558
435 1672610780179379
436 1754382364075724
437 1840056551148976
438 1929814252194161
439 2023845784157140
440 2122350452118582
441 2225534970970049
442 2333616804930545
443 2446823525450143
444 2565391309220230
445 2689568464080494
446 2819614813838813
447 2955800008872891
448 3098407541350269
449 3247733863683758
450 3404086805210763
451 3567789813239930
452 3739181092738732
453 3918611828829920
454 4106451001679278
455 4303084210995421
456 4508912043130474
457 4724355158608563
458 4949853130832722
459 5185862616408776
460 5432863114825078
461 5691355435935289
462 5961860064408187
463 6244923247566254
464 6541115468774367
465 6851029618403735
466 7175287868122629
467 7514539709161152
468 7869460380631240
469 8240758137779674
470 8629172286778033
471 9035471430900202
472 9460461658100782
473 9904984068327657
474 10369913357322915
475 10856166476138559
476 11364700144901303
477 11896509276600411
478 12452636710406047
479 13034170136673922
480 13642240959727921
481 14278034595528968
482 14942787373013407
483 15637785273212940
484 16364375480374746
485 17123962604034357
486 17918007984574475
487 18748041918276194
488 19615659846561026
489 20522521592753993
490 21470365049620781
491 22461001589598686
492 23496316027573369
493 24578281112392408
494 25708952897534373
495 26890470713818570
496 28125073366824062
497 29415093619938095
498 30762959092165020
499 32171209414035713
500 33642490668899279
501 35179556409895277
502 36785286805519574
503 38462682076750906
504 40214864686697451
505 42045099628508198
506 43956787826016136
507 45953468590496037
508 48038842229415266
509 50216762320114062
510 52491239646219691
511 54866466167891554
512 57346807275762936
513 59936806191274125
514 62641210644887367
515 65464963876701560
516 68413210896094988
517 71491326783167774
518 74704907703223533
519 78059777888499188
520 81562021100887402
521 85217970267188021
522 89034216788575091
523 93017643939820365
524 97175416576045216
525 101514991499172185
526 106044154550270948
527 110771008817409092
528 115703987906585263
529 120851895346415344
530 126223892958584367
531 131829515616263235
532 137678714967237236
533 143781846200056851
534 150149686415708692
535 156793481115085851
536 163724931264631125
537 170956213704732263
538 178500032692569192
539 186369605283291281
540 194578686221213681
541 203141622791975518
542 212073340701865213
543 221389371702062709
544 231105914366791720
545 241239818247944962
546 251808617047310664
547 262830593362758431
548 274324763622007760
549 286310914865973441
550 298809676452156396
551 311842503282862721
552 325431719439607560
553 339600594652760699
554 354373328698602857
555 369775099747050295
556 385832149013190145
557 402571763552799405
558 420022333053309361
559 438213440221230422
560 457175845278491678
561 476941548844820060
562 497543891965460293
563 519017539227918400
564 541398552030946217
565 564724495528769486
566 589034424165567034
567 614368962753030708
568 640770424796345422
569 668282797031551500
570 696951833259492915
571 726825181029001262
572 757952369547737050
573 790384913458007477
574 824176452986754739
575 859382741456846983
576 896061764706663371
577 934273891358962916
578 974081864968121027
579 1015550936024977962
580 1058749028195523069
581 1103746730950692889
582 1150617450730473704
583 1199437589459670992
584 1250286543468098323
585 1303246870507943553
586 1358404487251748970
587 1415848669949826883
588 1475672244884416155
589 1537971800793178036
590 1602847697970158634
591 1670404278605318886
592 1740750101824454014
593 1813997956265650920
594 1890265099057550125
595 1969673509039592230
596 2052349910567157486
597 2138426037341301637
598 2228038912639792170
599 2321330878959205447
600 2418449896806538356
601 2519549847115693283
602 2624790575701370193
603 2734338223009052108
604 2848365558867025576
605 2967052035936755215
606 3090584162107667856
607 3219155862368287815
608 3352968551655779600
609 3492231545708508110
610 3637162461737298097
611 3787987304447461404
612 3944940928868070529
613 4108267474225114262
614 4278220475210152794
615 4455063372465514173
616 4639069993119728887
617 4830524680693182695
618 5029722868891568841
619 5236971602847872901
620 5452589701698833197
621 5676908391303719505
622 5910271881725345836
623 6153037555534528133
624 6405576677593392003
625 6668275022506476757
626 6941533104988106217
627 7225766962364688821
628 7521408849946023972
629 7828907506257109636
630 8148729029301359759
631 8481357633340505481
632 8827295968031848259
633 9187066084279152853
634 9561210273197528159
635 9950291431815214111
636 10354894142946743241
637 10775625589693090503
638 11213115989936057496
639 11668019786412239991
640 12141016660835217714
641 12632812029858008563
642 13144138373753152569
643 13675756343517471343
644 14228455344289527321
645 14803054999401557533
646 15400406378438444510
647 16021392661018661739
648 16666930769277001138
649 17337972710452739442
650 18035506351460418593
651 18760557217461634542
652 19514189981521675146
653 20297509343401107290
654 21111662032737081702
655 21957838439832947518
656 22837273634347150100
657 23751249572027229644
658 24701096904551976965
659 25688196132451951200
660 26713980060335047367
661 27779935780699648570
662 28887606002980135708
663 30038591757992550673
664 31234554599987123679
665 32477218107551347927
666 33768370889767843065
667 35109869002755274381
668 36503637671692863258
669 37951674601838524269
670 39456052661331075411
671 41018921822103863537
672 42642512837155814324
673 44329140187811350454
674 46081204301535244790
675 47901195601823542807
676 49791697780579213610
677 51755390293443752485
678 53795052854202499175
679 55913569033211324658
680 58113929098651832263
681 60399234966039692925
682 62772704193896419526
683 65237673175421693233
684 67797602627406313599
685 70456081987831529832
686 73216833038728958301
687 76083715950561290144
688 79060734165455125501
689 82152038460918163872
690 85361933648665164130
691 88694883953190533790
692 92155517611832526224
693 95748634251141800060
694 99479210859378277688
695 103352406939395851097
696 107373572678911147139
697 111548255533262499058
698 115882206044143930898
699 120381386835841160328
700 125051979924552448465
701 129900393228281152572
702 134933270526002380904
703 140157499518530825084
704 145580219163516376029
705 151208830640973137529
706 157051006303111301279
707 163114697871107917878
708 169408148568418013531
709 175939902995719626591
710 182718816348365013012
711 189754067775226275189
712 197055171341369993102
713 204631986317355810352
714 212494731954092029527
715 220653999583684123757
716 229120764169293928416
717 237906400571718331034
718 247022696981127526989
719 256481867797016927628
720 266296571611537122898
721 276479926040744418824
722 287045522158976332067
723 298007444297079549308
724 309380286501871874796
725 321179168617608258773
726 333419758165260863273
727 346118288521794913141
728 359291576915638497570
729 372957048513080723536
730 387132756589110782759
731 401837402558557052304
732 417090362584746920620
733 432911709862413669851
734 449322237002351067009
735 466343485323035952090
736 483997769568891845311
737 502308202806315981529
738 521298728771808451175
739 540994149182285978785
740 561420151521273678588
741 582603344647085403771
742 604571289080215610312
743 627352527882549718175
744 650976625968805521223
745 675474203572831682465
746 700876970671582469533
747 727217770256225950669
748 754530615436370592712
749 782850727667414998763
750 812214584507688955738
751 842659960618533591235
752 874225970334124410310
753 906953120226119895979
754 940883354547334087686
755 976060102471525881101
756 1012528336091234261699
757 1050334620632472352619
758 1089527167008200476134
759 1130155895650749234928
760 1172272492151681074401
761 1215930465541308850965
762 1261185218700052260716
763 1308094109836768411268
764 1356716517263356828141
765 1407113916884436605544
766 1459349950295950513956
767 1513490496571529468224
768 1569603757716687026162
769 1627760333906824661942
770 1688033303204544032039
771 1750498315597658475065
772 1815233676311588825311
773 1882320434102221466144
774 1951842484933560419482
775 2023886664013754987166
776 2098542843762599239607
777 2175904047894627378105
778 2256066553297603657147
779 2339129998475829720944
780 2425197509297410076374
781 2514375811524080724592
782 2606775351044999401276
783 2702510432232700628021
784 2801699342463744057539
785 2904464485135425691615
786 3010932532131917271358
787 3121234561340082302977
788 3235506204022114204385
789 3353887812554082902932
790 3476524612541237514372
791 3603566865772279233936
792 3735170055022331770402
793 3871495052010998683354
794 4012708297820833698970
795 4158982006191799552005
796 4310494349244267202397
797 4467429656871433767327
798 4629978640665006689409
799 4798338598937948959216
800 4972713637344330763254
801 5153314915185087408239
802 5340360872034190666533
803 5534077471441045801663
804 5734698472172281639297
805 5942465678331335806455
806 6157629208841304406218
807 6380447795762121087371
808 6611189060665041296397
809 6850129812170403671549
810 7097556374394401510668
811 7353764891900548461773
812 7619061658522684475555
813 7893763478554079873734
814 8178198003586672355151
815 8472704095402312708557
816 8777632223554845836820
817 9093344836944141537136
818 9420216764643684188924
819 9758635653061611790799
820 10109002376219307587563
821 10471731477914287628854
822 10847251652824814173352
823 11236006198976984624099
824 11638453505874860775688
825 12055067583428104050958
826 12486338561367713441395
827 12932773227487586299553
828 13394895609614402686788
829 13873247526227782861831
830 14368389180359884663196
831 14880899799325089074116
832 15411378242252505018444
833 15960443654688484055047
834 16528736172328190926689
835 17116917590650486185428
836 17725672086865003391586
837 18355706993375141295066
838 19007753536359469658102
839 19682567631195731341775
840 20380930733121410582362
841 21103650651081327084427
842 21851562424580907126577
843 22625529258494733298140
844 23426443420386218593223
845 24255227206234268917552
846 25112833968320610491667
847 26000249103705660153192
848 26918491118349375008377
849 27868612756499392654961
850 28851702090160542862471
851 29868883690634865173273
852 30921319870093535058242
853 32010211881370584892005
854 33136801208319293759272
855 34302370929762394525179
856 35508247041401649822524
857 36755799875919106992484
858 38046445602084290719626
859 39381647680095063829152
860 40762918425065170245959
861 42191820653616026585922
862 43669969286780389923536
863 45199033070094804024419
864 46780736382960774071882
865 48416861002817340254423
866 50109247998163206964917
867 51859799715580140465687
868 53670481722106671041820
869 55543324887161587717466
870 57480427565510377211733
871 59483957734423105386111
872 61556155284031520447382
873 63699334414213986621784
874 65915885986820850180349
875 68208280043743904581062
876 70579068439581464568251
877 73030887428973537200022
878 75566460435748637528075
879 78188600943046186849834
880 80900215340052940652287
881 83704305965475546684751
882 86603974281260471081293
883 89602424002930127452959
884 92702964445324619433353
885 95909014006038511978645
886 99224103608440348055918
887 102651880377693539098027
888 106196111465160907641551
889 109860687833295537738737
890 113649628295351695548209
891 117567083712203523348152
892 121617341153918408690097
893 125804828336875476058229
894 130134118230352199321322
895 134609933629953757800265
896 139237152032076806728662
897 144020810688094506614988
898 148966111631295654295663
899 154078427029248260944828
900 159363304730221962671181
901 164826473785985587788782
902 170473850329797029048402
903 176311543660539599683387
904 182345862311203376640452
905 188583320501240503468360
906 195030644811748169068741
907 201694780850577700180305
908 208582900336073225132834
909 215702408417929620478586
910 223060950998509357154520
911 230666422506495379592473
912 238526973927127674901752
913 246651020840961369753575
914 255047251955531781369078
915 263724637910545324348525
916 272692440105298593646753
917 281960220058593699550276
918 291537849064954631351892
919 301435517884250393558920
920 311663747011166665044402
921 322233397261110821050648
922 333155680407142224743755
923 344442170443227539881138
924 356104815190648496202977
925 368155947970499166687548
926 380608299957770011355767
927 393475012902558474011234
928 406769651939788964712030
929 420506219135059246609967
930 434699167429036229977132
931 449363414690242212194325
932 464514358568456645561669
933 480167891775269477216325
934 496340417501316210248057
935 513048865698108434936653
936 530310709824054287799891
937 548143983752982303112262
938 566567299622517425246198
939 585599866180825327250404
940 605261507331307562221949
941 625572681692182348522587
942 646554502698181206714624
943 668228758933311959848189
944 690617935566332263506595
945 713745236369235997342556
946 737634606010949599743523
947 762310753541716156700084
948 787799176512260565299815
949 814126185410200289195663
950 841318929389642866934514
951 869405422684555496551309
952 898414571394062917404331
953 928376201664068338817229
954 959321088614007281370362
955 991280985688436220113840
956 1024288655524581156840828
957 1058377901623758492669912
958 1093583600515054955560474
959 1129941735555859767673343
960 1167489431609105810073583
961 1206264990278883196848510
962 1246307926922563324687708
963 1287659008610108001050204
964 1330360292724545206004404
965 1374455167480648674650259
966 1419988393477370048822264
967 1467006145973550844003721
968 1515556059244893579361516
969 1565687272059285759278452
970 1617450473976700775240663
971 1670897953896423526390528
972 1726083649825625586726192
973 1783063199573964861421385
974 1841893993885915720587048
975 1902635230896037468357483
976 1965347971633797174010090
977 2030095198160749858060917
978 2096941873153310025712522
979 2165955000659835387585320
980 2237203689712455140210918
981 2310759219506500147464829
982 2386695105904443756742972
983 2465087171022690282888459
984 2546013614532131640344422
985 2629555086436017365513785
986 2715794763190467366509654
987 2804818425685296703038694
988 2896714538884290764191647
989 2991574335075469976105838
990 3089491899155952600950064
991 3190564255762747458526692
992 3294891460317099082925861
993 3402576692279427705619332
994 3513726350470529825499021
995 3628450152619690685123114
996 3746861237331295665740668
997 3869076268344550419890648
998 3995215543374899560320748
999 4125403105585274954592960
1000 4259766857616394819281669