0 1
1 1
2 0
3 1
4 2
5 1
6 1
7 3
8 4
9 4
10 4
11 6
12 8
13 8
14 8
15 11
16 16
17 17
18 17
19 23
20 31
21 32
22 32
23 42
24 54
25 56
26 59
27 77
28 94
29 99
30 106
31 129
32 156
33 167
34 178
35 214
36 257
37 276
38 295
39 350
40 416
41 445
42 474
43 559
44 652
45 698
46 752
47 877
48 1012
49 1089
50 1174
51 1349
52 1542
53 1662
54 1792
55 2042
56 2327
57 2512
58 2706
59 3068
60 3472
61 3740
62 4026
63 4540
64 5106
65 5500
66 5933
67 6661
68 7446
69 8024
70 8656
71 9652
72 10744
73 11581
74 12482
75 13864
76 15384
77 16579
78 17857
79 19763
80 21856
81 23527
82 25318
83 27938
84 30782
85 33114
86 35643
87 39213
88 43070
89 46320
90 49827
91 54635
92 59838
93 64322
94 69140
95 75611
96 82643
97 88790
98 95365
99 104062
100 113475
101 121800
102 130720
103 142340
104 154874
105 166125
106 178215
107 193683
108 210298
109 225442
110 241689
111 262106
112 284070
113 304343
114 326030
115 352959
116 381933
117 408927
118 437751
119 473148
120 511184
121 546888
122 585010
123 631383
124 681076
125 728151
126 778474
127 838986
128 903722
129 965591
130 1031638
131 1110232
132 1194284
133 1275243
134 1361548
135 1463389
136 1572323
137 1677864
138 1790219
139 1921856
140 2062468
141 2199403
142 2345154
143 2514753
144 2695678
145 2872861
146 3061466
147 3279364
148 3511484
149 3740055
150 3983165
151 4262081
152 4559124
153 4853038
154 5165316
155 5521601
156 5900885
157 6277639
158 6677587
159 7131563
160 7614461
161 8095759
162 8606478
163 9183488
164 9796598
165 10409895
166 11060576
167 11792094
168 12568715
169 13348248
170 14174723
171 15099602
172 16081010
173 17069173
174 18116084
175 19282980
176 20520747
177 21770209
178 23093026
179 24562172
180 26119421
181 27694978
182 29362376
183 31207924
184 33162744
185 35145163
186 37242453
187 39555952
188 42004663
189 44493494
190 47125119
191 50018571
192 53079810
193 56197457
194 59492016
195 63104098
196 66923962
197 70820841
198 74936614
199 79437145
200 84193971
201 89054068
202 94185066
203 99781918
204 105693922
205 111743555
206 118128203
207 125075355
208 132409696
209 139925616
210 147853995
211 156460779
212 165543274
213 174862907
214 184689266
215 195333965
216 206562617
217 218097379
218 230253632
219 243396602
220 257253880
221 271503381
222 286515014
223 302715066
224 319787400
225 337360514
226 355867051
227 375802521
228 396801499
229 418436826
230 441212109
231 465703348
232 491491200
233 518083250
234 546064768
235 576107024
236 607727851
237 640358927
238 674681354
239 711476741
240 750189823
241 790166279
242 832200042
243 877199081
244 924523628
245 973424354
246 1024824774
247 1079775514
248 1137543171
249 1197270944
250 1260029106
251 1327034146
252 1397448854
253 1470292923
254 1546805196
255 1628395693
256 1714109014
257 1802821627
258 1895968635
259 1995184162
260 2099375337
261 2207258447
262 2320497914
263 2440982995
264 2567465100
265 2698482717
266 2835962866
267 2982084447
268 3135425219
269 3294325047
270 3461008867
271 3637989315
272 3823654032
273 4016115463
274 4217939754
275 4432027670
276 4656550378
277 4889360884
278 5133420483
279 5392075981
280 5663251811
281 5944510888
282 6239273000
283 6551393743
284 6878518270
285 7217890532
286 7573454509
287 7949641975
288 8343790803
289 8752789018
290 9181175365
291 9634044677
292 10108397304
293 10600719703
294 11116230658
295 11660789888
296 12231019910
297 12822951550
298 13442587215
299 14096664674
300 14781377623
301 15492253118
302 16236198320
303 17020949235
304 17842221926
305 18694990307
306 19587193882
307 20527701529
308 21511704337
309 22533566081
310 23602398010
311 24728365929
312 25906091598
313 27129254705
314 28408303520
315 29754895946
316 31163019516
317 32625588599
318 34154586710
319 35763376957
320 37445239442
321 39192246512
322 41018146462
323 42938241913
324 44945029654
325 47029667762
326 49207915527
327 51497273230
328 53889389468
329 56374420045
330 58970406073
331 61697360287
332 64546016246
333 67505422230
334 70596219452
335 73841297365
336 77230388159
337 80751312168
338 84427686679
339 88285684781
340 92313932430
341 96498917641
342 100867667638
343 105450082871
344 110233587180
345 115203234198
346 120389931275
347 125827805270
348 131502991902
349 137398996631
350 143551128777
351 149998331882
352 156725379900
353 163714087907
354 171004773944
355 178641885446
356 186608727210
357 194885273655
358 203517562195
359 212556305665
360 221983224195
361 231776322402
362 241988172340
363 252676598065
364 263821628382
365 275399189778
366 287469282244
367 300097784667
368 313262965160
369 326938546271
370 341192951060
371 356101227309
372 371639828262
373 387780127994
374 404600123256
375 422185308370
376 440510247715
377 459543813052
378 479374910155
379 500100912771
380 521694411289
381 544121679944
382 567484061614
383 591892395915
384 617317262898
385 643722280305
386 671222913313
387 699945255180
388 729857897594
389 760921753441
390 793268296176
391 827040948338
392 862206401678
393 898722801782
394 936739797492
395 976420526089
396 1017729851140
397 1060623120920
398 1105270660752
399 1151857988110
400 1200348251148
401 1250694075416
402 1303089314566
403 1357744846107
404 1414622305878
405 1473671781703
406 1535113820652
407 1599188004825
408 1665854815827
409 1735062035938
410 1807060454735
411 1882122233012
412 1960207183346
413 2041261071058
414 2125568991756
415 2213440100608
416 2304834095159
417 2399695106185
418 2498347198843
419 2601141487110
420 2708038215969
421 2818980510865
422 2934336714192
423 3054505441994
424 3179448395178
425 3309108547962
426 3443904432914
427 3584288419700
428 3730224865915
429 3881657642608
430 4039062117658
431 4202951588050
432 4373294598850
433 4550037143547
434 4733719004866
435 4924922586657
436 5123622354563
437 5329767947561
438 5543972230100
439 5766895892524
440 5998521401246
441 6238804046466
442 6488439615408
443 6748177385460
444 7018010396932
445 7297902126774
446 7588642285967
447 7891080330417
448 8205223107107
449 8531045272813
450 8869442835610
451 9221378703136
452 9586877425808
453 9965928360789
454 10359547891956
455 10768827442117
456 11193813767722
457 11634515114841
458 12092084284420
459 12567758169466
460 13061610995772
461 13573675121959
462 14105257954202
463 14657760869743
464 15231291930514
465 15825913908682
466 16443109187158
467 17084465068482
468 17750131107671
469 18440207896123
470 19156375725793
471 19900432243332
472 20672577611960
473 21472958835417
474 22303480142910
475 23166177226363
476 24061311312214
477 24989085943126
478 25951658867389
479 26951334968533
480 27988448736821
481 29063272417918
482 30178250764034
483 31335992858661
484 32536920847480
485 33781390118499
486 35072169992416
487 36412213174609
488 37802046530888
489 39242125353125
490 40735585820705
491 42285769077592
492 43893326662394
493 45558833186377
494 47285839600482
495 49078126182947
496 50936492091551
497 52861653832347
498 54857631451029
499 56928701426898
500 59075837038816
501 61299923378036
502 63605510998946
503 65997436690896
504 68476878843560
505 71044922320497
506 73706717132640
507 76467732614985
508 79329388436321
509 82293005295222
510 85364410283227
511 88549787127675
512 91850838798504
513 95269163317959
514 98811352643886
515 102484397409654
516 106290331975950
517 110231079677355
518 114314096682028
519 118547284578471
520 122933064502981
521 127473741041803
522 132177746731962
523 137054011098342
524 142105406126450
525 147334682527730
526 152751375185509
527 158365573224772
528 164180673736722
529 170199948089859
530 176434175288537
531 182894753011994
532 189585689000226
533 196510860788478
534 203682451600504
535 211113335708986
536 218808229295440
537 226771714302965
538 235017559026340
539 243560303353317
540 252405483892655
541 261558500637681
542 271034910897376
543 280851132552517
544 291013651527980
545 301528816644470
546 312414203291897
547 323688346337373
548 335358829226667
549 347433099355768
550 359931007868632
551 372873476387179
552 386269355886782
553 400127363389538
554 414469916342530
555 429320627174680
556 444689808045405
557 460587641382181
558 477039438646370
559 494071844791497
560 511696854306240
561 529926339866761
562 548788876050814
563 568314524258179
564 588517214335856
565 609410766750892
566 631027433683791
567 653401124568182
568 676547994265540
569 700484104704605
570 725245851593952
571 750871478902956
572 777379697117458
573 804789144176802
574 833140884004482
575 862478042606623
576 892822261968871
577 924195137328917
578 956642991743938
579 990214448330897
580 1024934508180653
581 1060828159675581
582 1097947649806718
583 1136347789296798
584 1176057425838446
585 1217105437863458
586 1259550742477774
587 1303455113769341
588 1348851801474733
589 1395774139097930
590 1444288552016898
591 1494464650661516
592 1546340718777008
593 1599955186546650
594 1655382930256522
595 1712702378116663
596 1771957564343022
597 1833192744888859
598 1896492307148509
599 1961944598647845
600 2029600217117384
601 2099510074016217
602 2171769259210396
603 2246477275499690
604 2323692207512456
605 2403472565057573
606 2485925476867704
607 2571162988156612
608 2659251719165445
609 2750258846873614
610 2844305038686438
611 2941516441248005
612 3041969399548806
613 3145740968528796
614 3252967038970836
615 3363789609380763
616 3478296094927354
617 3596574800188668
618 3718778731651024
619 3845067702894009
620 3975541721753278
621 4110301898370922
622 4249520478983270
623 4393377293042335
624 4541986665396778
625 4695464274071079
626 4854003985861233
627 5017808114039528
628 5187007252542271
629 5361733640319242
630 5542205434217294
631 5728650201142276
632 5921217011981758
633 6120056918675228
634 6325415363068544
635 6537548272300589
636 6756625686464405
637 6982820015655319
638 7216407346582270
639 7457675447396759
640 7706818141516178
641 7964032075344562
642 8229627747444252
643 8503928665940681
644 8787155615960410
645 9079532731811684
646 9381409142769062
647 9693148464584433
648 10015002033277007
649 10347225139503186
650 10690210269025280
651 11044366041266307
652 11409978392252422
653 11787337905518146
654 12176885719035700
655 12579080940680857
656 12994248668538801
657 13422719442752709
658 13864988987218475
659 14321573038197110
660 14792840995441265
661 15279168616432008
662 15781112856287154
663 16299252950525899
664 16834008392515090
665 17385806085800817
666 17955271652380908
667 18543055516528074
668 19149633789828318
669 19775491197046037
670 20421330347837529
671 21087881464097822
672 21775684620892316
673 22485289875348901
674 23217486138236308
675 23973093062775936
676 24752722946956841
677 25556999631498145
678 26386808751455881
679 27243070164758752
680 28126477679744002
681 29037738431402547
682 29977846439160972
683 30947833810492678
684 31948486307479558
685 32980605055330241
686 34045305492379801
687 35143745441285396
688 36276814358303600
689 37445419377398911
690 38650811926946284
691 39894290603167982
692 41176861746452506
693 42499551998422367
694 43863765068474132
695 45270957158199225
696 46722266298201242
697 48218853796267523
698 49762293853747004
699 51354219082299536
700 52995915820184998
701 54688697065634540
702 56434327861527184
703 58234638232293135
704 60091081474537166
705 62005141384804387
706 63978796573443478
707 66014097934224022
708 68112686647901889
709 70276238741895824
710 72506971772804007
711 74807183704053722
712 77178727067814808
713 79623494151823482
714 82143969801353874
715 84742728304070085
716 87421859841063915
717 90183499896744953
718 93030432251928677
719 95965540168215635
720 98991180940879599
721 102109763445142680
722 105324405722038276
723 108638336437329955
724 112054213011172132
725 115574751539213120
726 119203443733158029
727 122943904306668694
728 126799127778026079
729 130772175343785515
730 134866956351389932
731 139087516910206709
732 143437230028539066
733 147919544405130380
734 152538836068341670
735 157299633101951967
736 162205733316139566
737 167261020362516182
738 172470391652804451
739 177838913637069340
740 183370860733210908
741 189070604644324120
742 194943625159348880
743 200995589951859738
744 207231307992648756
745 213655698428124384
746 220274891404356359
747 227095225874218901
748 234122110154364592
749 241361077233993485
750 248818983373998393
751 256502916883913193
752 264418957848864086
753 272573327308387575
754 280973692057996700
755 289627976755882072
756 298543014163720586
757 307725796287774490
758 317184894513259511
759 326929166737462383
760 336966288769592144
761 347304116218380776
762 357952229819545782
763 368920528600606213
764 380217632341445492
765 391852363708500737
766 403835429430025466
767 416177889786349665
768 428889421206948632
769 441979928904219618
770 455461375452220383
771 469346116118570714
772 483645009740074036
773 498369172956363193
774 513531968734177420
775 529147196174984098
776 545227036817380775
777 561783962522049344
778 578832897521222927
779 596389250366792679
780 614466681776288427
781 633079179241534490
782 652243407256712286
783 671976568057914683
784 692293976038874554
785 713211313205221123
786 734747183409490307
787 756920787484932822
788 779749288042290743
789 803250261010032285
790 827444471019709692
791 852353345393687880
792 877996111778114396
793 904392462248281842
794 931565568432875582
795 959539337527385403
796 988335303765085153
797 1017975522962987827
798 1048485847487955897
799 1079892946056166994
800 1112220928539330408
801 1145494490311881014
802 1179742468745244120
803 1214994607073939115
804 1251277890431169290
805 1288619960905948734
806 1327052978970185117
807 1366610110155396760
808 1407321548444480186
809 1449218224584190132
810 1492335997773835822
811 1536711842224514177
812 1582379532059722086
813 1629373667249698311
814 1677734222987938478
815 1727502411331793590
816 1778715999660333202
817 1831413680621610922
818 1885640008837978590
819 1941440910780087348
820 1998858606632434787
821 2057936352816151691
822 2118723797974888038
823 2181272112082989702
824 2245628479237804052
825 2311841243574679025
826 2379965719001656103
827 2450058906301252847
828 2522173521794589434
829 2596363579870143936
830 2672690693725960141
831 2751218346789686827
832 2832005419351487970
833 2915112243573317249
834 3000607435546131398
835 3088561684640190961
836 3179040737153575655
837 3272111962616200026
838 3367851760680665097
839 3466338829057233511
840 3567646560043943774
841 3671850160080718062
842 3779034678367176334
843 3889287710922675911
844 4002691162472564798
845 4119328964500550706
846 4239295776140020491
847 4362689078644909945
848 4489600251390786916
849 4620122937167276326
850 4754362469939621844
851 4892427310487306118
852 5034419381167301386
853 5180443131041700603
854 5330615749504999664
855 5485057889933690534
856 5643883203473225229
857 5807208160846353490
858 5975163115499612876
859 6147882257850000541
860 6325492283754381782
861 6508123034399973051
862 6695919477512350560
863 6889030830295209335
864 7087598293349296184
865 7291766574809412293
866 7501696863459770797
867 7717555053758707820
868 7939498470611317668
869 8167688349002233480
870 8402303878701419304
871 8643529459672802656
872 8891540337213277270
873 9146516113892252599
874 9408655951879099036
875 9678164781410664859
876 9955237759504401537
877 10240074897157412628
878 10532897512037184027
879 10833933306577152978
880 11143399556862058828
881 11461518944592242730
882 11788537359958527156
883 12124707759487058355
884 12470271984645640112
885 12825477894978029666
886 13190598628629889275
887 13565915143293626420
888 13951696556400511977
889 14348218683166194926
890 14755784870645512273
891 15174707117809796835
892 15605284820751969304
893 16047824827421431167
894 16502663970191792684
895 16970148653051265150
896 17450611876244597534
897 17944394928284122948
898 18451871751677135007
899 18973426876485440071
900 19509430589346835184
901 20060262392785140333
902 20626337348928936130
903 21208082229471822424
904 21805908683928706080
905 22420238606183886330
906 23051532612047233484
907 23700264265944168865
908 24366891092265465563
909 25051881999682664248
910 25755748060437612686
911 26479014663617515244
912 27222190201447518680
913 27985795713432588747
914 28770398148331843748
915 29576580282390373695
916 30404906899581844329
917 31255956830278386231
918 32130358890697093761
919 33028759392037710200
920 33951785620169491113
921 34900080457028446129
922 35874341206960657734
923 36875284509569467347
924 37903606909929500332
925 38960022265166535543
926 40045303682899545652
927 41160245636752627520
928 42305621402538329918
929 43482223467657412043
930 44690908824089353775
931 45932558070596043136
932 47208029473246576418
933 48518202611816332328
934 49864027288400181980
935 51246479384016084052
936 52666511283630885114
937 54125099011774641392
938 55623295037641638495
939 57162180636178205618
940 58742812398543595517
941 60366273128465056729
942 62033728845616761744
943 63746377382612059366
944 65505390681368070072
945 67311969742096268637
946 69167406149319869074
947 71073026616505472596
948 73030130746593986970
949 75040050347277670267
950 77104215828587752498
951 79224096385705336979
952 81401132877788546804
953 83636801846783090543
954 85932687162052619588
955 88290415508804782885
956 90711584013560666614
957 93197829329473800987
958 95750904931653249768
959 98372611553724929929
960 101064719161088435976
961 103829041493195811971
962 106667519443087192676
963 109582146058207499434
964 112574882433595095834
965 115647738130660042602
966 118802861106590400735
967 122042456867670352579
968 125368697823186646998
969 128783810031251187319
970 132290170178695384152
971 135890218445160715629
972 139586360824456539838
973 143381062681609681960
974 147276953321528497334
975 151276732089543135076
976 155383063130630238050
977 159598676278392902750
978 163926479790838665450
979 168369459177947547809
980 172930563830779494252
981 177612815802163479802
982 182419431330385118170
983 187353711847153050347
984 192418921867725342138
985 197618406264419849973
986 202955721244697929972
987 208434516953584518970
988 214058405971766141575
989 219831089727180088614
990 225756499643522012541
991 231838670708942181003
992 238081599881248860652
993 244489382330560787435
994 251066363527644065232
995 257817003104892493974
996 264745722416726515120
997 271857051358098211686
998 279155792218801502932
999 286646873113470870992
1000 294335183891325191669