0 0
1 1
2 0
3 1
4 1
5 2
6 3
7 3
8 4
9 5
10 7
11 8
12 11
13 13
14 17
15 20
16 25
17 29
18 36
19 42
20 51
21 60
22 72
23 84
24 100
25 117
26 137
27 160
28 187
29 216
30 251
31 290
32 334
33 385
34 442
35 507
36 581
37 664
38 757
39 864
40 982
41 1116
42 1266
43 1435
44 1622
45 1835
46 2069
47 2333
48 2626
49 2954
50 3316
51 3724
52 4172
53 4673
54 5227
55 5844
56 6523
57 7280
58 8112
59 9036
60 10054
61 11180
62 12417
63 13788
64 15291
65 16950
66 18773
67 20779
68 22979
69 25401
70 28053
71 30966
72 34157
73 37655
74 41481
75 45676
76 50258
77 55270
78 60748
79 66731
80 73260
81 80390
82 88161
83 96635
84 105871
85 115929
86 126878
87 138798
88 151761
89 165855
90 181180
91 197825
92 215902
93 235530
94 256828
95 279929
96 304987
97 332140
98 361567
99 393443
100 427958
101 465312
102 505743
103 549465
104 596749
105 647861
106 703095
107 762753
108 827196
109 896751
110 971829
111 1052829
112 1140198
113 1234395
114 1335955
115 1445381
116 1563281
117 1690258
118 1826983
119 1974143
120 2132531
121 2302906
122 2486169
123 2683220
124 2895053
125 3122696
126 3367310
127 3630037
128 3912195
129 4215121
130 4540278
131 4889187
132 5263542
133 5665043
134 6095607
135 6557206
136 7051974
137 7582149
138 8150191
139 8758600
140 9410156
141 10107741
142 10854453
143 11653561
144 12508610
145 13423258
146 14401507
147 15447544
148 16565841
149 17761131
150 19038511
151 20403277
152 21861173
153 23418239
154 25080890
155 26855940
156 28750673
157 30772714
158 32930262
159 35231970
160 37687001
161 40305097
162 43096626
163 46072487
164 49244330
165 52624483
166 56225961
167 60062615
168 64149136
169 68501005
170 73134705
171 78067692
172 83318372
173 88906330
174 94852281
175 101178098
176 107906990
177 115063553
178 122673693
179 130764951
180 139366419
181 148508830
182 158224726
183 168548591
184 179516714
185 191167651
186 203542066
187 216682937
188 230635698
189 245448463
190 261171852
191 277859577
192 295568255
193 314357706
194 334291088
195 355435244
196 377860476
197 401641299
198 426856205
199 453588090
200 481924402
201 511957607
202 543784943
203 577509354
204 613239223
205 651088955
206 691179140
207 733637181
208 778597042
209 826200371
210 876596255
211 929941946
212 986403113
213 1046154624
214 1109380314
215 1176274364
216 1247041070
217 1321895778
218 1401065233
219 1484788556
220 1573317106
221 1666916093
222 1765864461
223 1870456037
224 1981000044
225 2097822320
226 2221265296
227 2351689940
228 2489475788
229 2635022339
230 2788749843
231 2951100770
232 3122540029
233 3303557258
234 3494667094
235 3696410902
236 3909357898
237 4134106965
238 4371287183
239 4621560550
240 4885622627
241 5164204630
242 5458075055
243 5768041901
244 6094953646
245 6439702514
246 6803225595
247 7186507452
248 7590582383
249 8016537142
250 8465512574
251 8938707504
252 9437380576
253 9962853452
254 10516513923
255 11099819325
256 11714298975
257 12361558916
258 13043284653
259 13761245145
260 14517297051
261 15313388967
262 16151565006
263 17033970577
264 17962856322
265 18940583155
266 19969627919
267 21052588770
268 22192190197
269 23391290129
270 24652885468
271 25980118454
272 27376284189
273 28844837467
274 30389399659
275 32013767589
276 33721921069
277 35518031044
278 37406469466
279 39391818022
280 41478877476
281 43672678734
282 45978493043
283 48401842421
284 50948512514
285 53624563859
286 56436344288
287 59390502938
288 62494003776
289 65754139027
290 69178545871
291 72775220938
292 76552536721
293 80519259302
294 84684566158
295 89058063543
296 93649807970
297 98470325008
298 103530630722
299 108842254243
300 114417261062
301 120268275458
302 126408508142
303 132851780571
304 139612552809
305 146705952366
306 154147804400
307 161954660795
308 170143835512
309 178733436068
310 187742399592
311 197190529674
312 207098535413
313 217488069014
314 228381770899
315 239803310499
316 251777432611
317 264330004618
318 277488066702
319 291279880415
320 305734986193
321 320884256011
322 336759952925
323 353395791485
324 370827002113
325 389090393821
326 408224427277
327 428269282830
328 449266936618
329 471261237881
330 494297991314
331 518425037805
332 543692347258
333 570152106148
334 597858814643
335 626869385505
336 657243249076
337 689042457127
338 722331800514
339 757178921691
340 793654438428
341 831832070053
342 871788771172
343 913604864846
344 957364191572
345 1003154253605
346 1051066372157
347 1101195848454
348 1153642133630
349 1208508999157
350 1265904725383
351 1325942286089
352 1388739548058
353 1454419476103
354 1523110348606
355 1594945975225
356 1670065935090
357 1748615812458
358 1830747449552
359 1916619207186
360 2006396237876
361 2100250763160
362 2198362374442
363 2300918333058
364 2408113890217
365 2520152617789
366 2637246753747
367 2759617554864
368 2887495676120
369 3021121552041
370 3160745801075
371 3306629644572
372 3459045343302
373 3618276644904
374 3784619262007
375 3958381355877
376 4139884046713
377 4329461943607
378 4527463695282
379 4734252556670
380 4950206990880
381 5175721281237
382 5411206174605
383 5657089550449
384 5913817114830
385 6181853116533
386 6461681104028
387 6753804698689
388 7058748404643
389 7377058452096
390 7709303670867
391 8056076393651
392 8417993407116
393 8795696926758
394 9189855615183
395 9601165643490
396 10030351789175
397 10478168573679
398 10945401455925
399 11432868059306
400 11941419450515
401 12471941473111
402 13025356125958
403 13602622993145
404 14204740740226
405 14832748656010
406 15487728256459
407 16170804957917
408 16883149805383
409 17625981267128
410 18400567108393
411 19208226325429
412 20050331154815
413 20928309169607
414 21843645443599
415 22797884800210
416 23792634156009
417 24829564943285
418 25910415623940
419 27036994311796
420 28211181479546
421 29434932772450
422 30710281936427
423 32039343847789
424 33424317654589
425 34867490052773
426 36371238667472
427 37938035568527
428 39570450924498
429 41271156786380
430 43042931008330
431 44888661334923
432 46811349619872
433 48814116212040
434 50900204510186
435 53072985681808
436 55335963550369
437 57692779688185
438 60147218673211
439 62703213553816
440 65364851519779
441 68136379779274
442 71022211643740
443 74026932865478
444 77155308180094
445 80412288106515
446 83803015999436
447 87332835359407
448 91007297399450
449 94832168921931
450 98813440451392
451 102957334685019
452 107270315253235
453 111759095800614
454 116430649383935
455 121292218250462
456 126351323935419
457 131615777750850
458 137093691655339
459 142793489520869
460 148723918791983
461 154894062609811
462 161313352334401
463 167991580547568
464 174938914524295
465 182165910195121
466 189683526593225
467 197503140869900
468 205636563805610
469 214096055910573
470 222894344101843
471 232044638985480
472 241560652738009
473 251456617681450
474 261747305474556
475 272448047026184
476 283574753117569
477 295143935769465
478 307172730348944
479 319678918522329
480 332680951973001
481 346197977002399
482 360249860003039
483 374857213846121
484 390041425181669
485 405824682770299
486 422230006762281
487 439281279056344
488 457003274729807
489 475421694590545
490 494563198853490
491 514455442073712
492 535127109251445
493 556607953255298
494 578928833561051
495 602121756364746
496 626219916079399
497 651257738362418
498 677270924589419
499 704296497936620
500 732372851077394
501 761539795559918
502 791838612885953
503 823312107452447
504 856004661275839
505 889962290677960
506 925232704949893
507 961865367071001
508 999911556515761
509 1039424434327422
510 1080459110384950
511 1123072713060033
512 1167324461296183
513 1213275739197088
514 1260990173174626
515 1310533711854019
516 1361974708672594
517 1415384007389709
518 1470835030558544
519 1528403871059397
520 1588169386767135
521 1650213298570254
522 1714620291693540
523 1781478120563593
524 1850877717292938
525 1922913303896459
526 1997682508339788
527 2075286484661164
528 2155830037137874
529 2239421748762445
530 2326174114134965
531 2416203676901134
532 2509631171870745
533 2606581672083616
534 2707184740820778
535 2811574588855126
536 2919890237085062
537 3032275684701407
538 3148880083062880
539 3269857915578450
540 3395369183627706
541 3525579598846548
542 3660660781968499
543 3800790468394903
544 3946152720720435
545 4096938148548000
546 4253344135665427
547 4415575074951503
548 4583842611256300
549 4758365892459000
550 4939371828990215
551 5127095362194740
552 5321779741659834
553 5523676811922102
554 5733047308865261
555 5950161166048204
556 6175297831322344
557 6408746594165577
558 6650806923920457
559 6901788819405521
560 7162013170292061
561 7431812130529776
562 7711529504267789
563 8001521144757812
564 8302155366504938
565 8613813371201299
566 8936889687929215
567 9271792627973919
568 9618944754793906
569 9978783369709347
570 10351761013667307
571 10738345985697921
572 11139022878662365
573 11554293132700305
574 11984675607047293
575 12430707170870634
576 12892943313594107
577 13371958775422838
578 13868348198801765
579 14382726801301636
580 14915731070746732
581 15468019483338959
582 16040273245384263
583 16633197059447604
584 17247519915829107
585 17883995909960925
586 18543405086708103
587 19226554312458605
588 19934278175768139
589 20667439917527143
590 21426932391729743
591 22213679057573814
592 23028635004077011
593 23872788008249616
594 24747159627782281
595 25652806329386118
596 26590820654084986
597 27562332420351092
598 28568509966503407
599 29610561433600958
600 30689736090017394
601 31807325699039017
602 32964665931048106
603 34163137821378476
604 35404169275542051
605 36689236623288947
606 38019866222957956
607 39397636117709702
608 40824177745510266
609 42301177704194766
610 43830379573637506
611 45413585796769288
612 47052659621222609
613 48749527103495738
614 50506179177867209
615 52324673791685035
616 54207138109443032
617 56155770787723196
618 58172844323166101
619 60260707475723551
620 62421787769852885
621 64658594075635550
622 66973719272689321
623 69369842999358273
624 71849734489797697
625 74416255501644532
626 77072363337436707
627 79821113962201569
628 82665665220618710
629 85609280156732011
630 88655330439367047
631 91807299896468249
632 95068788162116996
633 98443514439177211
634 101935321381608836
635 105548179100013228
636 109286189294204713
637 113153589516654850
638 117154757571272540
639 121294216051105988
640 125576637019755123
641 130006846840764837
642 134589831159553187
643 139330740042475232
644 144234893278318435
645 149307785846584708
646 154555093558230239
647 159982678873983320
648 165596596905691543
649 171403101606205800
650 177408652154079197
651 183619919538360411
652 190043793350197832
653 196687388787388281
654 203558053878388994
655 210663376932383112
656 218011194222836947
657 225609597910941115
658 233466944216882935
659 241591861846298985
660 249993260679690733
661 258680340732685498
662 267662601395955600
663 276949850962517042
664 286552216451813476
665 296480153739383497
666 306744458001391706
667 317356274483450450
668 328327109604166092
669 339668842402724942
670 351393736341646943
671 363514451475231670
672 376044056994756002
673 388996044161685783
674 402384339641256360
675 416223319247638949
676 430527822113855853
677 445313165299028778
678 460595158846123174
679 476390121303639368
680 492714895725875356
681 509586866165245185
682 527023974672225429
683 545044738817959108
684 563668269755177240
685 582914290833487936
686 602803156786341528
687 623355873505859182
688 644594118423941527
689 666540261517596216
690 689217386957101042
691 712649315416138098
692 736860627064384586
693 761876685261958664
694 787723660977503492
695 814428557951300258
696 842019238625527205
697 870524450864464238
698 899973855488880756
699 930398054647824261
700 961828621053570996
701 994298128105221261
702 1027840180927205183
703 1062489448349836197
704 1098281695860590227
705 1135253819553858952
706 1173443881109638501
707 1212891143831489037
708 1253636109774935608
709 1295720557998589571
710 1339187583971914760
711 1384081640172757201
712 1430448577910658329
713 1478335690412025951
714 1527791757204141678
715 1578867089836366237
716 1631613578978665052
717 1686084742936938408
718 1742335777627736948
719 1800423608055230866
720 1860406941334278021
721 1922346321305142917
722 1986304184787315211
723 2052344919519439782
724 2120534923835692718
725 2190942668129499835
726 2263638758156558957
727 2338696000231218580
728 2416189468372307275
729 2496196573454332610
730 2578797134423535653
731 2664073451639179244
732 2752110382401625588
733 2842995418731287184
734 2936818767464756803
735 3033673432734557166
736 3133655300902795148
737 3236863228020295876
738 3343399129884096901
739 3453368074769229524
740 3566878378913139880
741 3684041704831611949
742 3804973162549221950
743 3929791413829101577
744 4058618779488264330
745 4191581349888385796
746 4328809098694597867
747 4470435999995821038
748 4616600148884685266
749 4767443885597387937
750 4923113923315519301
751 5083761479736202755
752 5249542412519865121
753 5420617358726442093
754 5597151878355781188
755 5779316602110934258
756 5967287383504972076
757 6161245455437058295
758 6361377591366835423
759 6567876271218298591
760 6780939852149783078
761 7000772744330357591
762 7227585591865185633
763 7461595459018412838
764 7703026021885887215
765 7952107765672875322
766 8209078187737967429
767 8474182006568891417
768 8747671376858623187
769 9029806110857210120
770 9320853906178988893
771 9621090580248591698
772 9930800311575856011
773 10250275888055261076
774 10579818962488691524
775 10919740315538529336
776 11270360126322964620
777 11632008250870135261
778 12005024508655227384
779 12389758977451325972
780 12786572296728599520
781 13195835979845944595
782 13617932735284869629
783 14053256797181271445
784 14502214265419243753
785 14965223455559027949
786 15442715258875773463
787 15935133512796857140
788 16442935382032071791
789 16966591750698225000
790 17506587625749303551
791 18063422552032846340
792 18637611039298666675
793 19229683001498892774
794 19840184208725966199
795 20469676752144029473
796 21118739522280086550
797 21787968701052562090
798 22477978267921515671
799 23189400520559606932
800 23922886610451901366
801 24679107093843206912
802 25458752498464176679
803 26262533906480660589
804 27091183554118810506
805 27945455448435572794
806 28826126001714784200
807 29733994683981790803
808 30669884694143921393
809 31634643650279721700
810 32629144299609547997
811 33654285248699868778
812 34710991714466115518
813 35800216296554043774
814 36922939771696202890
815 38080171910658355750
816 39272952318402395214
817 40502351298115066147
818 41769470739766555462
819 43075445033880949258
820 44421442011219805244
821 45808663909101409568
822 47238348365092418241
823 48711769438834779290
824 50230238662788298443
825 51795106122690392096
826 53407761568556904114
827 55069635557072741407
828 56782200626238097334
829 58546972503166187236
830 60365511345949095001
831 62239423020533268898
832 64170360413572177892
833 66160024782252604223
834 68210167142111520356
835 70322589693895185815
836 72499147290536577515
837 74741748945356568902
838 77052359382624508467
839 79433000631647549603
840 81885753665582653022
841 84412760086205080748
842 87016223855896189187
843 89698413078147661724
844 92461661827914585026
845 95308372033188930587
846 98241015409194432425
847 101262135446649755496
848 104374349455581138763
849 107580350666205882960
850 110882910388449199114
851 114284880231702398364
852 117789194386465594249
853 121398871969570885051
854 125117019434722542822
855 128946833050137687511
856 132891601445118965872
857 136954708227443523387
858 141139634673494526105
859 145449962493122252994
860 149889376671269692467
861 154461668388452376366
862 159170738022238306641
863 164020598231935025975
864 169015377128740860358
865 174159321533687295851
866 179456800325756002704
867 184912307882617931482
868 190530467616507450953
869 196316035607815472110
870 202273904339044877125
871 208409106531852091709
872 214726819089965327938
873 221232367150844482799
874 227931228249024251545
875 234829036594164293716
876 241931587466900695716
877 249244841735685731314
878 256774930497881452326
879 264528159848459362397
880 272511015779747846993
881 280730169215764406834
882 289192481184753089938
883 297905008133654388022
884 306875007388327266505
885 316109942763443927313
886 325617490326082298153
887 335405544317151802756
888 345482223234886430038
889 355855876084762335342
890 366535088800305787323
891 377528690839374697929
892 388845761960618816016
893 400495639184951798545
894 412487923946984531087
895 424832489441511163231
896 437539488170266777755
897 450619359694312191825
898 464082838597543505265
899 477940962666972540741
900 492205081295561108074
901 506886864113555963193
902 521998309854420788774
903 537551755461620307565
904 553559885442677352882
905 570035741477095873095
906 586992732284903688607
907 604444643762758049243
908 622405649394732081192
909 640890320945084796259
910 659913639440510439338
911 679491006449562488610
912 699638255667136495767
913 720371664812114423405
914 741707967846477966922
915 763664367524412847010
916 786258548280150960046
917 809508689463528576633
918 833433478932460235908
919 858052127011780332165
920 883384380828143813115
921 909450539030926621993
922 936271466909328324078
923 963868611916147448316
924 992264019608959448554
925 1021480350019718729163
926 1051540894464085778311
927 1082469592802069951499
928 1114291051161883015396
929 1147030560139209326896
930 1180714113484401914357
931 1215368427290450639721
932 1251020959694894855497
933 1287699931109189163886
934 1325434344989385038277
935 1364254009162351260205
936 1404189557722110617486
937 1445272473511259755146
938 1487535111202819358294
939 1531010720998252218817
940 1575733472957798294980
941 1621738481979693341796
942 1669061833445251475925
943 1717740609547242254332
944 1767812916319435815757
945 1819317911385642788551
946 1872295832447053683673
947 1926788026527166329377
948 1982836979994072389106
949 2040486349380394584592
950 2099780993021681797221
951 2160767003534595136366
952 2223491741156772999063
953 2288003867970823810927
954 2354353383035457256976
955 2422591658447366777894
956 2492771476358075693437
957 2564947066970569548647
958 2639174147541181143675
959 2715509962412844370422
960 2794013324106487275527
961 2874744655498030894263
962 2957766033109157248613
963 3043141231540717752113
964 3130935769078399988828
965 3221216954501023478567
966 3314053935122596023741
967 3409517746100067277146
968 3507681361039525478199
969 3608619743934404213269
970 3712409902470131624594
971 3819130942730526309736
972 3928864125342128566167
973 4041692923093586583259
974 4157703080068156553096
975 4276982672328327396889
976 4399622170192583675354
977 4525714502145329946852
978 4655355120422026921582
979 4788642068312666293152
980 4925676049227800770571
981 5066560497572448910405
982 5211401651474355809631
983 5360308627414259812246
984 5513393496807007401419
985 5670771364583603194821
986 5832560449825545200256
987 5998882168504073625331
988 6169861218378306036373
989 6345625666107585065976
990 6526307036634747388386
991 6712040404898461770241
992 6902964489934247727505
993 7099221751425266789263
994 7300958488765534165067
995 7508324942699764965905
996 7721475399605671640547
997 7940568298486192854541
998 8165766340740829137759
999 8397236602786974965807
1000 8635150651603936468680