0 1
1 0
2 0
3 1
4 1
5 1
6 1
7 2
8 2
9 3
10 3
11 4
12 5
13 6
14 7
15 9
16 10
17 12
18 15
19 17
20 20
21 24
22 28
23 32
24 38
25 44
26 51
27 59
28 68
29 78
30 91
31 103
32 118
33 136
34 155
35 176
36 201
37 228
38 259
39 294
40 332
41 375
42 425
43 478
44 538
45 607
46 681
47 764
48 858
49 961
50 1075
51 1203
52 1343
53 1499
54 1673
55 1863
56 2073
57 2308
58 2564
59 2847
60 3161
61 3504
62 3882
63 4301
64 4757
65 5260
66 5814
67 6419
68 7083
69 7814
70 8611
71 9484
72 10443
73 11488
74 12631
75 13884
76 15247
77 16737
78 18366
79 20138
80 22071
81 24181
82 26474
83 28972
84 31695
85 34651
86 37866
87 41366
88 45163
89 49287
90 53770
91 58628
92 63900
93 69622
94 75818
95 82534
96 89814
97 97690
98 106218
99 115452
100 125433
101 136227
102 147904
103 160514
104 174139
105 188861
106 204746
107 221894
108 240405
109 260361
110 281884
111 305094
112 330099
113 357041
114 386070
115 417318
116 450959
117 487174
118 526127
119 568030
120 613101
121 661542
122 713611
123 769572
124 829675
125 894228
126 963552
127 1037955
128 1117809
129 1203500
130 1295406
131 1393973
132 1499671
133 1612958
134 1734372
135 1864479
136 2003835
137 2153090
138 2312922
139 2484009
140 2667129
141 2863096
142 3072734
143 3296975
144 3536797
145 3793193
146 4067279
147 4360233
148 4673247
149 5007659
150 5364877
151 5746337
152 6153639
153 6588465
154 7052541
155 7547776
156 8076178
157 8639819
158 9240973
159 9882038
160 10565490
161 11294039
162 12070543
163 12897960
164 13779514
165 14718607
166 15718763
167 16783820
168 17917818
169 19124957
170 20409789
171 21777112
172 23231924
173 24779621
174 26425893
175 28176676
176 30038359
177 32017688
178 34121699
179 36357956
180 38734437
181 41259476
182 43942019
183 46791492
184 49817757
185 53031374
186 56443473
187 60065711
188 63910540
189 67991092
190 72321119
191 76915297
192 81789100
193 86958740
194 92441493
195 98255571
196 104420064
197 110955294
198 117882673
199 125224657
200 133005122
201 141249218
202 149983339
203 159235505
204 169035234
205 179413506
206 190403179
207 202038867
208 214356894
209 227395760
210 241196008
211 255800190
212 271253378
213 287603014
214 304898906
215 323193758
216 342543042
217 363005004
218 384641222
219 407516500
220 431698880
221 457260250
222 484276253
223 512826301
224 542994252
225 574868314
226 608541093
227 644110327
228 681678794
229 721354394
230 763250939
231 807488085
232 854191452
233 903493460
234 955533307
235 1010457107
236 1068418814
237 1129580230
238 1194111173
239 1262190489
240 1334006100
241 1409755214
242 1489645445
243 1573894873
244 1662732342
245 1756398662
246 1855146727
247 1959241888
248 2068963245
249 2184603852
250 2306471143
251 2434888362
252 2570194851
253 2712746534
254 2862917517
255 3021100436
256 3187707061
257 3363170050
258 3547943381
259 3742503090
260 3947349184
261 4163006201
262 4390024085
263 4628980274
264 4880480414
265 5145159373
266 5423683559
267 5716751790
268 6025096470
269 6349486165
270 6690726645
271 7049662260
272 7427178812
273 7824204769
274 8241712897
275 8680723426
276 9142305508
277 9627579129
278 10137718579
279 10673954224
280 11237574692
281 11829930745
282 12452437371
283 13106576286
284 13793900270
285 14516035595
286 15274684933
287 16071632189
288 16908745307
289 17787979659
290 18711383399
291 19681100755
292 20699375931
293 21768559051
294 22891110013
295 24069602945
296 25306732859
297 26605320121
298 27968315531
299 29398807787
300 30900028625
301 32475358664
302 34128335740
303 35862660819
304 37682204707
305 39591017352
306 41593334658
307 43693586173
308 45896405459
309 48206637952
310 50629349720
311 53169839081
312 55833645637
313 58626560218
314 61554637934
315 64624208497
316 67841887559
317 71214591362
318 74749548486
319 78454312817
320 82336779909
321 86405200452
322 90668195014
323 95134772347
324 99814344795
325 104716745016
326 109852246532
327 115231581289
328 120865958613
329 126767088298
330 132947200559
331 139419067570
332 146196029365
333 153292016496
334 160721574487
335 168499892868
336 176642830937
337 185166945478
338 194089523293
339 203428610492
340 213203043847
341 223432487308
342 234137465243
343 245339397872
344 257060642281
345 269324530065
346 282155407414
347 295578681158
348 309620861333
349 324309606549
350 339673775608
351 355743475700
352 372550113663
353 390126453845
354 408506672660
355 427726416410
356 447822866233
357 468834799769
358 490802656340
359 513768609874
360 537776638495
361 562872598063
362 589104303978
363 616521609674
364 645176489563
365 675123130731
366 706418021520
367 739120044970
368 773290581601
369 808993609317
370 846295808592
371 885266677738
372 925978645471
373 968507189247
374 1012930964536
375 1059331931540
376 1107795488336
377 1158410615794
378 1211270020138
379 1266470282708
380 1324112022328
381 1384300055690
382 1447143565710
383 1512756283364
384 1581256668100
385 1652768096920
386 1727419068096
387 1805343403948
388 1886680463100
389 1971575368710
390 2060179236178
391 2152649411456
392 2249149726603
393 2349850755377
394 2454930080714
395 2564572580730
396 2678970715623
397 2798324827669
398 2922843461258
399 3052743684794
400 3188251426985
401 3329601834963
402 3477039635256
403 3630819510604
404 3791206500615
405 3958476406319
406 4132916212346
407 4314824535002
408 4504512075461
409 4702302092621
410 4908530904020
411 5123548393414
412 5347718540153
413 5581419978989
414 5825046568404
415 6079007982942
416 6343730338813
417 6619656829919
418 6907248390382
419 7206984393526
420 7519363363325
421 7844903715295
422 8184144537206
423 8537646384558
424 8905992108895
425 9289787729438
426 9689663322363
427 10106273946440
428 10540300615905
429 10992451294292
430 11463461928369
431 11954097533894
432 12465153305779
433 12997455772630
434 13551864008177
435 14129270870874
436 14730604292831
437 15356828630998
438 16008946050843
439 16687997964848
440 17395066539103
441 18131276237406
442 18897795426100
443 19695838053471
444 20526665372341
445 21391587729816
446 22291966438936
447 23229215699705
448 24204804594397
449 25220259172946
450 26277164594480
451 27377167351247
452 28521977591471
453 29713371505874
454 30953193805744
455 32243360309455
456 33585860601359
457 34982760792090
458 36436206397878
459 37948425302049
460 39521730828623
461 41158524946926
462 42861301568994
463 44632649971007
464 46475258359025
465 48391917539168
466 50385524725324
467 52459087505507
468 54615727925745
469 56858686726458
470 59191327753174
471 61617142499583
472 64139754819371
473 66762925829774
474 69490558963968
475 72326705210119
476 75275568561569
477 78341511633947
478 81529061488733
479 84842915689489
480 88287948544887
481 91869217580359
482 95591970265905
483 99461650952795
484 103483908063471
485 107664601563325
486 112009810666173
487 116525841819833
488 121219237001933
489 126096782277059
490 131165516663479
491 136432741341701
492 141906029154699
493 147593234450291
494 153502503300349
495 159642284044970
496 166021338215178
497 172648751870679
498 179533947299499
499 186686695136436
500 194117126938410
501 201835748162999
502 209853451609793
503 218181531364948
504 226831697194618
505 235816089449585
506 245147294524449
507 254838360815860
508 264902815245434
509 275354680393841
510 286208492189235
511 297479318219650
512 309182776718624
513 321335056166323
514 333952935580085
515 347053805546360
516 360655689935972
517 374777268380725
518 389437899566425
519 404657645284324
520 420457295322838
521 436858393258733
522 453883263089241
523 471555036791462
524 489897682872850
525 508936035853333
526 528695826771035
527 549203714779518
528 570487319776786
529 592575256164131
530 615497167806679
531 639283764136640
532 663966857502901
533 689579401843700
534 716155532624383
535 743730608149506
536 772341252332011
537 802025398861894
538 832822336890253
539 864772758317890
540 897918806631211
541 932304127409170
542 967973920596527
543 1004974994487326
544 1043355821550753
545 1083166596200954
546 1124459294456899
547 1167287735632674
548 1211707646167129
549 1257776725541652
550 1305554714434929
551 1355103465232251
552 1406487014840570
553 1459771659967706
554 1515026034992767
555 1572321192381453
556 1631730685815706
557 1693330656174246
558 1757199920321011
559 1823420062883223
560 1892075531165194
561 1963253733159872
562 2037045138851999
563 2113543384970009
564 2192845383154530
565 2275051431749862
566 2360265331388575
567 2448594504342641
568 2540150117861672
569 2635047211682592
570 2733404829690001
571 2835346155964187
572 2940998655415286
573 3050494218990430
574 3163969313708433
575 3281565137735515
576 3403427780498462
577 3529708388107670
578 3660563334320671
579 3796154397053165
580 3936648940729156
581 4082220104720060
582 4233046997890899
583 4389314899566421
584 4551215467188124
585 4718946950692284
586 4892714413945691
587 5072729963532121
588 5259212984933552
589 5452390386469020
590 5652496851307370
591 5859775097614686
592 6074476147226460
593 6296859603186652
594 6527193936233446
595 6765756780650412
596 7012835239854678
597 7268726201821720
598 7533736664797422
599 7808184073701092
600 8092396667340496
601 8386713836925400
602 8691486496316870
603 9007077464158098
604 9333861858412240
605 9672227503780376
606 10022575352174050
607 10385319916808758
608 10760889720431498
609 11149727757888606
610 11552291973644043
611 11969055754805997
612 12400508439901802
613 12847155844059824
614 13309520801204811
615 13788143723543663
616 14283583179053978
617 14796416487633516
618 15327240336229259
619 15876671413716783
620 16445347066243802
621 17033925973403660
622 17643088846071773
623 18273539146680125
624 18926003832347866
625 19601234121767892
626 20300006286692515
627 21023122468492507
628 21771411520762760
629 22545729878892098
630 23346962457132529
631 24176023574222405
632 25033857908560488
633 25921441483534268
634 26839782684145569
635 27789923306015929
636 28772939637451754
637 29789943575806606
638 30842083779317437
639 31930546855178973
640 33056558585195474
641 34221385190290836
642 35426334634731965
643 36672757971516637
644 37962050730320082
645 39295654348954260
646 40675057649914141
647 42101798363526929
648 43577464698768006
649 45103696963451660
650 46682189235444519
651 48314691086087140
652 50003009357675779
653 51749009996796810
654 53554619944832879
655 55421829087648508
656 57352692266406411
657 59349331350978506
658 61413937378129455
659 63548772756597178
660 65756173540692061
661 68038551774779322
662 70398397910955717
663 72838283301715970
664 75360862770176709
665 77968877260371188
666 80665156569602117
667 83452622165639450
668 86334290091497551
669 89313273959989240
670 92392788041080671
671 95576150445024078
672 98866786403693588
673 102268231653407147
674 105784135922475707
675 109418266526152838
676 113174512072551380
677 117056886283053457
678 121069531930159491
679 125216724896651032
680 129502878359903188
681 133932547104591729
682 138510431968002649
683 143241384422117996
684 148130411296050032
685 153182679643392715
686 158403521759033689
687 163798440349353804
688 169373113860777126
689 175133401971616437
690 181085351251527883
691 187235200993967514
692 193589389227029990
693 200154558907405947
694 206937564303318295
695 213945477572289952
696 221185595538942670
697 228665446679193325
698 236392798317214661
699 244375664040865920
700 252622311342508138
701 261141269492132911
702 269941337649058951
703 279031593219708640
704 288421400469004458
705 298120419392236449
706 308138614855564625
707 318486266013357668
708 329173976009871272
709 340212681974138019
710 351613665316988131
711 363388562338417158
712 375549375154938996
713 388108482956625763
714 401078653602826669
715 414473055567036071
716 428305270241464265
717 442589304611145873
718 457339604308961023
719 472571067063048785
720 488299056547364191
721 504539416647739037
722 521308486155929523
723 538623113903401041
724 556500674348280325
725 574959083629047077
726 594016816097804677
727 613692921347719739
728 634007041749387007
729 654979430510144719
730 676630970272187887
731 698983192265524815
732 722058296031088909
733 745879169731220169
734 770469411064961891
735 795853348804882631
736 822056064974124433
737 849103417682640480
738 877022064640853950
739 905839487371053263
740 935584016137132921
741 966284855612569062
742 997972111308693650
743 1030676816785665551
744 1064430961667829137
745 1099267520487420788
746 1135220482380966384
747 1172324881662014913
748 1210616829296228763
749 1250133545305284570
750 1290913392125352138
751 1332995908948410089
752 1376421847075139761
753 1421233206307472572
754 1467473272411477628
755 1515186655681812437
756 1564419330638320883
757 1615218676888096462
758 1667633521186927722
759 1721714180733434931
760 1777512507732068757
761 1835081935261813198
762 1894477524486857632
763 1955756013248504467
764 2018975866078328383
765 2084197325672059278
766 2151482465866815524
767 2220895246165142799
768 2292501567848813409
769 2366369331728657246
770 2442568497577607272
771 2521171145293697765
772 2602251537843234285
773 2685886186035362656
774 2772153915178880782
775 2861135933675790245
776 2952915903607203717
777 3047580013366902216
778 3145217052401679118
779 3245918488118844877
780 3349778545021012329
781 3456894286132331964
782 3567365696781704789
783 3681295770808329384
784 3798790599259206479
785 3919959461649713108
786 4044914919858284917
787 4173772914730736552
788 4306652865471386541
789 4443677771898186178
790 4584974319643780841
791 4730672988386233812
792 4880908163193287683
793 5035818249069026232
794 5195545788793778801
795 5360237584148376554
796 5530044820619138801
797 5705123195682132660
798 5885633050765658097
799 6071739506995477442
800 6263612604829672857
801 6461427447690586170
802 6665364349707173305
803 6875608987683692278
804 7092352557411392279
805 7315791934446077789
806 7546129839477255854
807 7783575008415510966
808 8028342367331315775
809 8280653212381586659
810 8540735394861433210
811 8808823511525503076
812 9085159100326704345
813 9369990841721459529
814 9663574765698010322
815 9966174464687974036
816 10278061312522985621
817 10599514689606056339
818 10930822214471296392
819 11272279981907564656
820 11624192807829866255
821 11986874481086702937
822 12360648022393798632
823 12745845950593380198
824 13142810556442972951
825 13551894184140216961
826 13973459520799507650
827 14407879894101464486
828 14855539578339144471
829 15316834109094790677
830 15792170606786559086
831 16281968109327986546
832 16786657914153444875
833 17306683929868975715
834 17842503037791662944
835 18394585463651829848
836 18963415159739042473
837 19549490197777136377
838 20153323172825316188
839 20775441618509659074
840 21416388433894101731
841 22076722322312582367
842 22757018242491916276
843 23457867872300299276
844 24179880085469736737
845 24923681441649276127
846 25689916690151862388
847 26479249287771897984
848 27292361931059906803
849 28129957103447320089
850 28992757637629583476
851 29881507293625905792
852 30796971352941315842
853 31739937229272868426
854 32711215096212828012
855 33711638532409791786
856 34742065184665962016
857 35803377449460690250
858 36896483173399414114
859 38022316373105503584
860 39181837975085443958
861 40376036576107727100
862 41605929224655440430
863 42872562224026540032
864 44177011957666762966
865 45520385737341059644
866 46903822674764605130
867 48328494577326518498
868 49795606868561757048
869 51306399534043103522
870 52862148093378425988
871 54464164599022251234
872 56113798662628508146
873 57812438509685859496
874 59561512063202535236
875 61362488057226864536
876 63216877181005684421
877 65126233254610039407
878 67092154436878465780
879 69116284466545669110
880 71200313937453505929
881 73345981608763791385
882 75555075751111618294
883 77829435529668989866
884 80170952425113044341
885 82581571693514094891
886 85063293866191997746
887 87618176290615836782
888 90248334713444798231
889 92955944906843727177
890 95743244339235487794
891 98612533891677242222
892 101566179621085869919
893 104606614571568715155
894 107736340635143118752
895 110957930463168968248
896 114274029429851993237
897 117687357649205250693
898 121200712046899902166
899 124816968488472599566
900 128539083965389158745
901 132370098840510958923
902 136313139154549644476
903 140371418995130936066
904 144548242930138447031
905 148847008507050686667
906 153271208820022772128
907 157824435146518023550
908 162510379655340306967
909 167332838187959686129
910 172295713115081421192
911 177403016270457722684
912 182658871963986976523
913 188067520076206753329
914 193633319236340248826
915 199360750086105003840
916 205254418631558788561
917 211319059685315124917
918 217559540401514340026
919 223980863906006844608
920 230588173024267501009
921 237386754109617927401
922 244382040974409490232
923 251579618926886857476
924 258985228916514885851
925 266604771790633002010
926 274444312665373700863
927 282510085413849976844
928 290808497274703793561
929 299346133584185910332
930 308129762635011282207
931 317166340665327891980
932 326463016981221264439
933 336027139216256977108
934 345866258731663944997
935 355988136160852298406
936 366400747102046395973
937 377112287962921293808
938 388131181961229205285
939 399466085285496385486
940 411125893419986507773
941 423119747638232547652
942 435457041669540808433
943 448147428542994808974
944 461200827613601024829
945 474627431775328406916
946 488437714865926782641
947 502642439268532457614
948 517252663715188241661
949 532279751297548071434
950 547735377690169233724
951 563631539591923780381
952 579980563391214150081
953 596795114060821211622
954 614088204288351953492
955 631873203848418718855
956 650163849222836254015
957 668974253475273056558
958 688318916386970286774
959 708212734860307886207
960 728671013597159831835
961 749709476059170245808
962 771344275717261366454
963 793592007597859678667
964 816469720133530268111
965 839994927325902628784
966 864185621228960461402
967 889060284760986761993
968 914637904853663608949
969 940937985947030447080
970 967980563839239531698
971 995786219900271390129
972 1024376095658993764021
973 1053771907773199671034
974 1083995963392501714100
975 1115071175924197816021
976 1147021081212494340435
977 1179869854141732628516
978 1213642325674521815426
979 1248364000335971555793
980 1284061074155498324617
981 1320760453077956020516
982 1358489771856153803458
983 1397277413437125622319
984 1437152528854814700011
985 1478145057642171468068
986 1520285748775988079302
987 1563606182168114813993
988 1608138790717063657453
989 1653916882934353802172
990 1700974666160301146784
991 1749347270384340406711
992 1799070772685344601737
993 1850182222307781049018
994 1902719666389958066968
995 1956722176361021408165
996 2012229875023762895529
997 2069283964340749429512
998 2127926753941716166058
999 2188201690370602390727
1000 2250153387091087175209