0 1
1 0
2 1
3 1
4 2
5 2
6 5
7 4
8 9
9 10
10 16
11 19
12 31
13 34
14 53
15 64
16 89
17 109
18 152
19 180
20 246
21 298
22 388
23 473
24 612
25 732
26 935
27 1125
28 1402
29 1685
30 2086
31 2478
32 3041
33 3610
34 4366
35 5169
36 6213
37 7295
38 8712
39 10202
40 12068
41 14083
42 16571
43 19221
44 22500
45 26014
46 30244
47 34850
48 40338
49 46256
50 53313
51 60941
52 69875
53 79623
54 90952
55 103232
56 117499
57 132970
58 150728
59 170092
60 192186
61 216158
62 243491
63 273136
64 306643
65 343103
66 384119
67 428582
68 478554
69 532675
70 593114
71 658693
72 731649
73 810571
74 898280
75 993058
76 1097872
77 1211245
78 1336234
79 1471095
80 1619616
81 1779677
82 1955277
83 2144606
84 2351771
85 2574669
86 2818311
87 3080150
88 3365479
89 3672141
90 4005575
91 4363303
92 4751870
93 5168277
94 5619444
95 6102866
96 6625642
97 7184931
98 7789176
99 8434930
100 9131125
101 9874926
102 10675500
103 11529668
104 12448204
105 13427240
106 14478180
107 15597916
108 16798144
109 18075411
110 19443339
111 20897694
112 22452897
113 24105644
114 25870724
115 27744511
116 29744066
117 31864897
118 34125071
119 36521223
120 39071880
121 41773387
122 44646956
123 47687979
124 50918905
125 54336492
126 57963761
127 61797245
128 65863103
129 70156825
130 74706101
131 79508055
132 84591083
133 89952172
134 95623373
135 101600556
136 107917625
137 114572405
138 121599672
139 128997229
140 136804088
141 145016860
142 153676807
143 162782859
144 172377331
145 182459292
146 193075947
147 204225120
148 215956707
149 228271264
150 241219976
151 254803733
152 269079340
153 284046399
154 299764921
155 316237723
156 333526358
157 351634232
158 370629338
159 390513766
160 411359304
161 433171794
162 456024886
163 479925317
164 504954072
165 531116578
166 558498287
167 587109000
168 617036383
169 648291494
170 680970353
171 715082732
172 750729879
173 787926637
174 826776881
175 867297157
176 909600796
177 953703127
178 999723578
179 1047683327
180 1097704903
181 1149811699
182 1204136945
183 1260702921
184 1319649911
185 1381006930
186 1444917907
187 1511414686
188 1580653247
189 1652664464
190 1727612474
191 1805535865
192 1886603037
193 1970856111
194 2058477033
195 2149507163
196 2244137808
197 2342419149
198 2444547465
199 2550577275
200 2660720045
201 2775029787
202 2893728702
203 3016880847
204 3144714174
205 3277298015
206 3414877308
207 3557521215
208 3705486912
209 3858854958
210 4017889189
211 4182676491
212 4353499653
213 4530445797
214 4713811626
215 4903697171
216 5100406784
217 5304048030
218 5514946372
219 5733210094
220 5959180425
221 6192980213
222 6434959475
223 6685249948
224 6944225088
225 7212017942
226 7489019777
227 7775380045
228 8071500046
229 8377539634
230 8693926116
231 9020821337
232 9358672664
233 9707660362
234 10068243227
235 10440613636
236 10825259149
237 11222374945
238 11632471123
239 12055763486
240 12492775110
241 12943735798
242 13409200418
243 13889402505
244 14384922154
245 14896015956
246 15423278697
247 15966983085
248 16527758951
249 17105883793
250 17702015647
251 18316457707
252 18949884591
253 19602617945
254 20275370964
255 20968471310
256 21682663594
257 22418304073
258 23176156034
259 23956596756
260 24760431918
261 25588046187
262 26440280194
263 27317550350
264 28220718234
265 29150224127
266 30106976120
267 31091423450
268 32104512974
269 33146729088
270 34219042128
271 35321963470
272 36456514402
273 37623217006
274 38823135488
275 40056830815
276 41325393402
277 42629414624
278 43970040638
279 45347875474
280 46764112704
281 48219399262
282 49714957952
283 51251469854
284 52830218634
285 54451900218
286 56117850554
287 57828812842
288 59586155526
289 61390660018
290 63243761167
291 65146257643
292 67099641832
293 69104764390
294 71163153763
295 73275703268
296 75444013659
297 77668998200
298 79952320863
299 82294951973
300 84698595432
301 87164269038
302 89693755371
303 92288095133
304 94949140207
305 97677993845
306 100476552060
307 103345970818
308 106288231595
309 109304516502
310 112396882909
311 115566581363
312 118815717910
313 122145601473
314 125558430831
315 129055544630
316 132639224576
317 136310884101
318 140072858514
319 143926625732
320 147874621562
321 151918357536
322 156060359982
323 160302222022
324 164646528871
325 169094944750
326 173650163662
327 178313887716
328 183088909536
329 187977020105
330 192981076679
331 198102948443
332 203345610278
333 208710973900
334 214202121494
335 219821061475
336 225570946796
337 231453871738
338 237473116307
339 243630822351
340 249930386461
341 256374055531
342 262965303566
343 269706471548
344 276601170533
345 283651794556
346 290862081172
347 298234538406
348 305772988325
349 313480041850
350 321359668781
351 329414539010
352 337648759409
353 346065123395
354 354667829979
355 363459784936
356 372445346308
357 381627485263
358 391010708197
359 400598119959
360 410394327252
361 420402557381
362 430627588128
363 441072719109
364 451742888430
365 462641540233
366 473773721672
367 485143010165
368 496754636683
369 508612258395
370 520721279382
371 533085512856
372 545710481285
373 558600142694
374 571760216885
375 585194749665
376 598909647477
377 612909124443
378 627199215379
379 641784291509
380 656670599297
381 671862606349
382 687366760190
383 703187709765
384 719332041580
385 735804574798
386 752612122724
387 769759610156
388 787254066711
389 805100612338
390 823306426992
391 841876814770
392 860819198446
393 880138997650
394 899843867648
395 919939437895
396 940433526026
397 961331960479
398 982642818653
399 1004372055096
400 1026527996829
401 1049116823746
402 1072147038088
403 1095625034473
404 1119559592756
405 1143957244995
406 1168827038793
407 1194175748017
408 1220012609097
409 1246344627309
410 1273181335594
411 1300529888733
412 1328400106575
413 1356799403112
414 1385737801479
415 1415222964793
416 1445265232569
417 1475872430319
418 1507055204724
419 1538821658889
420 1571182658112
421 1604146573356
422 1637724607299
423 1671925307013
424 1706760203679
425 1742238141409
426 1778370886248
427 1815167570019
428 1852640318217
429 1890798453348
430 1929654451980
431 1969217954157
432 2009501688509
433 2050515603765
434 2092272811255
435 2134783465909
436 2178061053857
437 2222116069220
438 2266962268400
439 2312610476347
440 2359074856617
441 2406366456805
442 2454499840325
443 2503486416772
444 2553341039032
445 2604075470935
446 2655704998232
447 2708241624872
448 2761701062792
449 2816095701952
450 2871441564106
451 2927751418107
452 2985041745586
453 3043325574016
454 3102619838929
455 3162937979117
456 3224297261337
457 3286711529296
458 3350198538011
459 3414772409382
460 3480451381461
461 3547250014061
462 3615186899103
463 3684277028709
464 3754539512798
465 3825989642421
466 3898647041146
467 3972527465929
468 4047650918022
469 4124033615507
470 4201696108895
471 4280654937083
472 4360931196373
473 4442541920962
474 4525508609939
475 4609848788972
476 4695584539113
477 4782733729992
478 4871319022201
479 4961358811523
480 5052876187756
481 5145890070017
482 5240424164405
483 5336497758410
484 5434135173014
485 5533356254273
486 5634185780167
487 5736644153593
488 5840756804740
489 5946544530601
490 6054033413367
491 6163244842561
492 6274205386584
493 6386937026960
494 6501467021906
495 6617817774182
496 6736017232822
497 6856088428756
498 6978059827937
499 7101955090169
500 7227803410564
501 7355628898705
502 7485461481236
503 7617325933234
504 7751252730450
505 7887267315533
506 8025400934540
507 8165679509968
508 8308135061959
509 8452794217573
510 8599689579907
511 8748848484114
512 8900304346602
513 9054085013972
514 9210224721249
515 9368752060524
516 9529701885200
517 9693103537938
518 9858992730402
519 10027399349891
520 10198359973240
521 10371905276016
522 10548072490635
523 10726893087682
524 10908405204719
525 11092640891859
526 11279639200485
527 11469433013744
528 11662062077515
529 11857560116448
530 12055967830584
531 12257319560683
532 12461656971416
533 12669015283344
534 12879436896399
535 13092957921293
536 13309621763185
537 13529465187303
538 13752532616502
539 13978861744645
540 14208497772504
541 14441479334901
542 14677852691170
543 14917657170891
544 15160940106408
545 15407741806961
546 15658110427430
547 15912087271130
548 16169721607043
549 16431055475383
550 16696139275915
551 16965016081728
552 17237737161764
553 17514346638628
554 17794896953264
555 18079433009339
556 18368008438732
557 18660669233536
558 18957469943564
559 19258457668268
560 19563688189771
561 19873209434764
562 20187078439072
563 20505344275716
564 20828064949316
565 21155290700631
566 21487080829388
567 21823486451924
568 22164568186988
569 22510378357580
570 22860978604420
571 23216422481164
572 23576772988996
573 23942084607664
574 24312421725412
575 24687840091547
576 25068405171688
577 25454174011412
578 25845213504825
579 26241581676357
580 26643346877986
581 27050568469162
582 27463315937105
583 27881650005872
584 28305641661853
585 28735352663098
586 29170855527547
587 29612213416455
588 30059500043267
589 30512780004986
590 30972128587797
591 31437611480215
592 31909305576597
593 32387278039593
594 32871607021888
595 33362361195972
596 33859620363645
597 34363454348962
598 34873944641576
599 35391162613437
600 35915191077961
601 36446102993987
602 36983982903479
603 37528904979449
604 38080955534454
605 38640210366137
606 39206757178952
607 39780673437610
608 40362048657541
609 40950961582870
610 41547503585663
611 42151755114392
612 42763809003929
613 43383747453151
614 44011665193508
615 44647645771311
616 45291785863910
617 45944170804831
618 46604898808027
619 47274057044017
620 47951745712169
621 48638053401236
622 49333082349240
623 50036923018198
624 50749679259414
625 51471443461893
626 52202321554527
627 52942407418305
628 53691809116959
629 54450622494063
630 55218957306434
631 55996911418050
632 56784596758911
633 57582112761702
634 58389573591072
635 59207080735041
636 60034750134183
637 60872685393942
638 61721004727215
639 62579813387940
640 63449231927165
641 64329367750353
642 65220343270623
643 66122268111522
644 67035267061182
645 67959451474649
646 68894948585511
647 69841872000153
648 70800350903621
649 71770501224783
650 72752454630198
651 73746328866463
652 74752258156796
653 75770362602605
654 76800778471382
655 77843628295329
656 78899050933677
657 79967170825993
658 81048129503405
659 82142053867522
660 83249087590058
661 84369360115654
662 85503017822003
663 86650192154186
664 87811032281075
665 88985672220951
666 90174263383187
667 91376942445459
668 92593863641314
669 93825165745477
670 95071005906275
671 96331525586735
672 97606884279294
673 98897226226903
674 100202713868528
675 101523493644481
676 102859731036349
677 104211575291990
678 105579194344536
679 106962740346576
680 108362384304363
681 109778280671872
682 111210603630364
683 112659510564784
684 114125178219204
685 115607767012566
686 117107456893011
687 118624410688802
688 120158811659965
689 121710825693448
690 123280638727460
691 124868419816695
692 126474358238838
693 128098625569785
694 129741414540691
695 131402899918326
696 133083277231419
697 134782724552927
698 136501440891068
699 138239606955935
700 139997425355597
701 141775080127704
702 143572776801613
703 145390702864345
704 147229067469379
705 149088060861037
706 150967895943956
707 152868766431403
708 154790888277279
709 156734458792268
710 158699697703937
711 160686805204687
712 162696004929589
713 164727500686129
714 166781519291096
715 168858268302497
716 170957978465163
717 173080860347692
718 175227148763963
719 177397058048671
720 179590826334428
721 181808671864639
722 184050836859491
723 186317542706356
724 188609035861231
725 190925541633664
726 193267309940086
727 195634570162257
728 198027576468816
729 200446561523483
730 202891783902998
731 205363480354430
732 207861913061450
733 210387323012208
734 212939976812550
735 215520118875391
736 218128020392422
737 220763930026398
738 223428122727390
739 226120851573601
740 228842396112673
741 231593012995212
742 234372986538243
743 237182577814076
744 240022075054531
745 242891743927439
746 245791877443155
747 248722744994608
748 251684644550819
749 254677850103789
750 257702663699023
751 260759364109859
752 263848258346992
753 266969629066659
754 270123788433498
755 273311023885896
756 276531651831856
757 279785964682899
758 283074284004733
759 286396906254813
760 289754158354165
761 293146341731216
762 296573787722771
763 300036802928234
764 303535724040515
765 307070861873426
766 310642558682819
767 314251130448285
768 317896924019345
769 321580260750595
770 325301493052275
771 329060946667332
772 332858979782956
773 336695923508725
774 340572140809109
775 344487968379129
776 348443774954726
777 352439901798919
778 356476723645174
779 360554587330179
780 364673872554113
781 368834931955996
782 373038151224728
783 377283887752739
784 381572533453628
785 385904451506940
786 390280038988389
787 394699665103447
788 399163733140249
789 403672617248989
790 408226727176621
791 412826443080348
792 417472180070740
793 422164324561298
794 426903298105428
795 431689492258785
796 436523335274589
797 441405224942101
798 446335595085935
799 451314849988952
800 456343430155843
801 461421745215210
802 466550242619809
803 471729338465217
804 476959485989666
805 482241108026801
806 487574664739160
807 492960584516125
808 498399334723764
809 503891350458726
810 509437105093287
811 515037040713848
812 520691637868353
813 526401344415409
814 532166648369447
815 537988004543793
816 543865907186389
817 549800818359482
818 555793239745370
819 561843639401597
820 567952526747522
821 574120377050068
822 580347706196357
823 586634996968969
824 592982772955435
825 599391523163577
826 605861779196354
827 612394037533103
828 618988836485699
829 625646680323601
830 632368115332876
831 639153652245069
832 646003845647990
833 652919214014389
834 659900318889322
835 666947686818108
836 674061887601437
837 681243454490723
838 688492965882870
839 695810963047906
840 703198031595607
841 710654721159054
842 718181625893160
843 725779302388350
844 733448353698426
845 741189344717804
846 749002885976250
847 756889551030042
848 764849959251606
849 772884691413210
850 780994376097433
851 789179602673934
852 797441007471966
853 805779188830272
854 814194792226602
855 822688423481983
856 831260737604106
857 839912349313098
858 848643921641856
859 857456078595402
860 866349492669415
861 875324795625192
862 884382669817086
863 893523756215598
864 902748745486682
865 912058288210399
866 921453084838405
867 930933793989007
868 940501126310180
869 950155749948110
870 959898384157013
871 969729707026222
872 979650447927375
873 989661293278084
874 999762982993175
875 1009956213345650
876 1020241733159389
877 1030620248993350
878 1041092520129575
879 1051659261753569
880 1062321244046801
881 1073079192386575
882 1083933886174820
883 1094886061426926
884 1105936508352799
885 1117085971901140
886 1128335253547090
887 1139685108776759
888 1151136348605706
889 1162689739519765
890 1174346103701765
891 1186106216886171
892 1197970912896604
893 1209940978359845
894 1222017256968750
895 1234200546721254
896 1246491702846191
897 1258891532914300
898 1271400904180750
899 1284020635472986
900 1296751604253230
901 1309594641101375
902 1322550635394186
903 1335620427617480
904 1348804919569948
905 1362104963368267
906 1375521471365195
907 1389055307821335
908 1402707397392378
909 1416478614587100
910 1430369896889181
911 1444382130822248
912 1458516264780432
913 1472773197833054
914 1487153891075723
915 1501659254177590
916 1516290261478733
917 1531047835057299
918 1545932960529802
919 1560946572932344
920 1576089670991772
921 1591363200705148
922 1606768174471148
923 1622305551100234
924 1637976354643161
925 1653781557291397
926 1669722196625405
927 1685799256168534
928 1702013787611293
929 1718366787705295
930 1734859320178851
931 1751492395598504
932 1768267091652360
933 1785184430619655
934 1802245504747961
935 1819451349970398
936 1836803070968079
937 1854301717934185
938 1871948409950672
939 1889744209314313
940 1907690250127322
941 1925787608776813
942 1944037432204756
943 1962440811514785
944 1980998908501791
945 1999712826774279
946 2018583743619789
947 2037612777184796
948 2056801118013257
949 2076149899436166
950 2095660327313953
951 2115333547894220
952 2135170783014241
953 2155173193918503
954 2175342016128147
955 2195678426552033
956 2216183676502748
957 2236858956228285
958 2257705533514338
959 2278724614076201
960 2299917479821837
961 2321285352622713
962 2342829530665116
963 2364551249593072
964 2386451824574387
965 2408532507202618
966 2430794627217414
967 2453239452872606
968 2475868330684930
969 2498682543125310
970 2521683454213029
971 2544872362862674
972 2568250648126318
973 2591819626095351
974 2615580693109945
975 2639535179934537
976 2663684500945443
977 2688030003857150
978 2712573118551344
979 2737315210448501
980 2762257727241845
981 2787402049492357
982 2812749643476077
983 2838301907222805
984 2864060322998237
985 2890026307080334
986 2916201360082436
987 2942586913902321
988 2969184488295883
989 2995995533161096
990 3023021584739965
991 3050264111733887
992 3077724669281501
993 3105404742195307
994 3133305905329684
995 3161429662041642
996 3189777604180241
997 3218351254474636
998 3247152224232671
999 3276182052798089
1000 3305442371781301