0 1
1 0
2 1
3 0
4 2
5 2
6 3
7 2
8 5
9 4
10 7
11 6
12 11
13 10
14 15
15 14
16 22
17 22
18 30
19 30
20 44
21 44
22 58
23 60
24 81
25 84
26 107
27 112
28 145
29 154
30 190
31 202
32 253
33 270
34 327
35 352
36 429
37 462
38 550
39 594
40 711
41 770
42 904
43 980
44 1156
45 1256
46 1457
47 1586
48 1845
49 2008
50 2310
51 2516
52 2898
53 3160
54 3604
55 3930
56 4488
57 4894
58 5545
59 6050
60 6858
61 7480
62 8426
63 9190
64 10353
65 11292
66 12653
67 13796
68 15460
69 16852
70 18799
71 20488
72 22849
73 24890
74 27657
75 30118
76 33451
77 36416
78 40315
79 43868
80 48548
81 52800
82 58269
83 63350
84 69876
85 75930
86 83553
87 90750
88 99805
89 108352
90 118914
91 129032
92 141534
93 153500
94 168058
95 182184
96 199347
97 215988
98 235955
99 255528
100 278986
101 301982
102 329221
103 356180
104 388091
105 419660
106 456655
107 493570
108 536775
109 579876
110 629896
111 680148
112 738401
113 796930
114 864256
115 932318
116 1010536
117 1089600
118 1179850
119 1271582
120 1376173
121 1482470
122 1602975
123 1726010
124 1865338
125 2007612
126 2167871
127 2332178
128 2517090
129 2706664
130 2919026
131 3137526
132 3382038
133 3633620
134 3914017
135 4203398
136 4525611
137 4858178
138 5227115
139 5608916
140 6032110
141 6470060
142 6953899
143 7455800
144 8009793
145 8584472
146 9216973
147 9874408
148 10597380
149 11348898
150 12173146
151 13031442
152 13972085
153 14951580
154 16022515
155 17139432
156 18359664
157 19632290
158 21019710
159 22468628
160 24047088
161 25695538
162 27487903
163 29361920
164 31398169
165 33527140
166 35836369
167 38253248
168 40873010
169 43614826
170 46582153
171 49690446
172 53052260
173 56573730
174 60376907
175 64363746
176 68666983
177 73177836
178 78040275
179 83140744
180 88635579
181 94399124
182 100600901
183 107109670
184 114109499
185 121455490
186 129346983
187 137632812
188 146529360
189 155869878
190 165888699
191 176412018
192 187693896
193 199543060
194 212234614
195 225569132
196 239844838
197 254842744
198 270885425
199 287744860
200 305770656
201 324712630
202 344948966
203 366219420
204 388933459
205 412806212
206 438280504
207 465060072
208 493624335
209 523649616
210 555654015
211 589301360
212 625152446
213 662840400
214 702971221
215 745164400
216 790075356
217 837289712
218 887515660
219 940323632
220 996479520
221 1055516452
222 1118261449
223 1184231380
224 1254320484
225 1328004290
226 1406248416
227 1488511010
228 1575835545
229 1667635104
230 1765036313
231 1867433472
232 1976043974
233 2090213080
234 2211254600
235 2338494292
236 2473351595
237 2615098750
238 2765267575
239 2923110320
240 3090281212
241 3265974998
242 3451976795
243 3647460720
244 3854354432
245 4071770640
246 4301788721
247 4543501366
248 4799153770
249 5067772898
250 5351780734
251 5650185386
252 5965601066
253 6296967000
254 6647103067
255 7014931252
256 7403495134
257 7811645118
258 8242663420
259 8695386776
260 9173357542
261 9675338402
262 10205149490
263 10761544970
264 11348646675
265 11965134312
266 12615452870
267 13298279936
268 14018411485
269 14774451810
270 15571571886
271 16408383860
272 17290466788
273 18216361990
274 19192084974
275 20216197934
276 21295189849
277 22427558500
278 23620300435
279 24871950504
280 26190055971
281 27573097046
282 29029210354
283 30556935400
284 32165049034
285 33852049596
286 35627399543
287 37489684756
288 39449110875
289 41504242978
290 43666084131
291 45933321444
292 48317822277
293 50818280360
294 53447489096
295 56204309352
296 59102539287
297 62141081378
298 65334811110
299 68682853912
300 72201252009
301 75889219848
302 79764052414
303 83825255120
304 88091479685
305 92562380980
306 97258066092
307 102178566574
308 107345566760
309 112759322932
310 118443212133
311 124397972312
312 130648812493
313 137196792010
314 144069088255
315 151267368950
316 158820941552
317 166731915440
318 175031884975
319 183723724704
320 192841505150
321 202388689568
322 212402008105
323 222885879020
324 233879908873
325 245389288462
326 257456716444
327 270088566688
328 283330881865
329 297191033020
330 311718655695
331 326922581796
332 342856333685
333 359530012560
334 377001317986
335 395282146214
336 414434711927
337 434472514144
338 455462623325
339 477420732446
340 500419159898
341 524475604730
342 549668026676
343 576016800160
344 603605983329
345 632458440830
346 662664787919
347 694251139552
348 727315194320
349 761886143558
350 798069305558
351 835897805556
352 875485192194
353 916868369700
354 960169737371
355 1005430951308
356 1052783971807
357 1102275072240
358 1154046495970
359 1208150240388
360 1264739651066
361 1323872347640
362 1385713620595
363 1450327964320
364 1517893563807
365 1588481732858
366 1662284525695
367 1739381499528
368 1819979681410
369 1904166868056
370 1992166192769
371 2084075314394
372 2180134745631
373 2280452075710
374 2385286516494
375 2494757429004
376 2609144199583
377 2728578122328
378 2853360285145
379 2983636012708
380 3119729806383
381 3261801289314
382 3410200149314
383 3565102701910
384 3726885797307
385 3895742849182
386 4072079931357
387 4256110278818
388 4448271476615
389 4648797159296
390 4858158807025
391 5076613561130
392 5304669448481
393 5542607893580
394 5790976234656
395 6050083730286
396 6320520090162
397 6602623431304
398 6897029043335
399 7204107949208
400 7524544558674
401 7858744126696
402 8207443892377
403 8571087967580
404 8950470518743
405 9346076189872
406 9758760370549
407 10189053527928
408 10637877003455
409 11105809187966
410 11593842352886
411 12102608853458
412 12633177355992
413 13186236792070
414 13762937973414
415 14364033317940
416 14990762101867
417 15643943431970
418 16324911701235
419 17034560616848
420 17774326975963
421 18545182998672
422 19348675583145
423 20185864506310
424 21058415181653
425 21967479697952
426 22914850868358
427 23901783446832
428 24930207363695
429 26001485767854
430 27117695970723
431 28280321376698
432 29491597878171
433 30753136021750
434 32067342140182
435 33435967491904
436 34861601767895
437 36346145188732
438 37892384479515
439 39502384364880
440 41179143505683
441 42924900955384
442 44742883090963
443 46635521104380
444 48606286249365
445 50657813536280
446 52793837303247
447 55017216765682
448 57331969119050
449 59741191634424
450 62249205340673
451 64859368919446
452 67576330014627
453 70403725074960
454 73346552532344
455 76408753366678
456 79595703010978
457 82911666263820
458 86362423414275
459 89952593723122
460 93688392505046
461 97574816185624
462 101618547160540
463 105824994125100
464 110201341276101
465 114753436215510
466 119489001837389
467 124414364873144
468 129537826825355
469 134866224772648
470 140408481285725
471 146171989842546
472 152166339967112
473 158399518067790
474 164881829431753
475 171621906142740
476 178630821994259
477 185917897391016
478 193495030744045
479 201372291193386
480 209562462336927
481 218076411782602
482 226927872805574
483 236128580635400
484 245693287780671
485 255634655019868
486 265968528147078
487 276708572662604
488 287871807505865
489 299472970239558
490 311530337975212
491 324059810979064
492 337081016148100
493 350611094668600
494 364671120823632
495 379279580429852
496 394459100245402
497 410229601469392
498 426615375281505
499 443637896935826
500 461323242548137
501 479694546560956
502 498779798407743
503 518603927499800
504 539196974694507
505 560585786068640
506 582802601090664
507 605876337774740
508 629841592441385
509 654729495784734
510 680577169606508
511 707418134838706
512 735292220024640
513 764235498891270
514 794290699881331
515 825496652527848
516 857899192667860
517 891540093260776
518 926468518722255
519 962729417437856
520 1000375519881870
521 1039455166237844
522 1080024906159885
523 1122136736732200
524 1165851298502686
525 1211224494715138
526 1258321346410961
527 1307201965862014
528 1357936065309500
529 1410588253007972
530 1465233263627476
531 1521940547261464
532 1580790216216483
533 1641856892540370
534 1705226444804430
535 1770979061896290
536 1839206774607564
537 1909995718075760
538 1983444518010185
539 2059645706557994
540 2138704968055267
541 2220721667462802
542 2305809042064800
543 2394073803954340
544 2485637272903525
545 2580614008388868
546 2679133977102923
547 2781320172629438
548 2887311813099680
549 2997240899966750
550 3111256547103249
551 3229500432981236
552 3352132256994643
553 3479304032337580
554 3611186779153347
555 3747943608199006
556 3889757647208802
557 4036803857978568
558 4189278314417205
559 4347368698810344
560 4511284928508730
561 4681228268857154
562 4857423436832089
563 5040086271524200
564 5229457312260130
565 5425767958817342
566 5629275662777447
567 5840228512985846
568 6058902038658655
569 6285562146327738
570 6520503684617655
571 6764011662634328
572 7016401575900743
573 7277978825900860
574 7549080969422567
575 7830035263006276
576 8121202836212560
577 8422934273914000
578 8735615888848855
579 9059623258656424
580 9395369599759532
581 9743257164548008
582 10103727905970092
583 10477212644674030
584 10864184027890518
585 11265103363658452
586 11680476078839391
587 12110796122327618
588 12556603927434685
589 13018428272604744
590 13496846969443382
591 13992426074150442
592 14505783308701497
593 15037524501967420
594 15588309982915924
595 16158788135588862
596 16749664774171078
597 17361633680336216
598 17995449218388155
599 18651853729111698
600 19331653397362498
601 20035642360014464
602 20764682104794723
603 21519622155453360
604 22301383017510855
605 23110873286178160
606 23949076439840476
607 24816964222374316
608 25715587303473825
609 26645984767691000
610 27609278966613768
611 28606580953562014
612 29639089550451807
613 30707992546674530
614 31814570331400082
615 32960092681669400
616 34145926987651239
617 35373430433254104
618 36644063192662925
619 37959275813947890
620 39320627419332096
621 40729668078498388
622 42188062421101031
623 43697466794201820
624 45259658324836611
625 46876406630867624
626 48549608774298851
627 50281155302442998
628 52073071136349640
629 53927375692435476
630 55846230181165708
631 57831791567672504
632 59886366332009951
633 62012257998050630
634 64211927868125946
635 66487835858503388
636 68842608267296946
637 71278871623917372
638 73799428043219880
639 76407081805195616
640 79104822363300545
641 81895643337754552
642 84782733774037991
643 87769289242911620
644 90858711426688608
645 94054410983224200
646 97360016102887668
647 100779166804239182
648 104315732549828105
649 107973597603317400
650 111756888397126163
651 115669749591074432
652 119716581292390205
653 123901805415574160
654 128230113501426250
655 132706222989130574
656 137335135748094166
657 142121883829299258
658 147071799515084400
659 152190250128928694
660 157482919731420943
661 162955532521138056
662 168614147044329591
663 174464867731489160
664 180514151765808109
665 186768508250556358
666 193234818670693393
667 199920023199228558
668 206831454915099250
669 213976512702933680
670 221363010234337049
671 228998834929458216
672 236892311884456624
673 245051848306371200
674 253486313471614016
675 262204668059406144
676 271216360346702407
677 280530939804948168
678 290158470699518610
679 300109129329577544
680 310393635261801294
681 321022831527478220
682 332008134749101660
683 343361097624919300
684 355093878204698378
685 367218783922458530
686 379748761376653839
687 392696921187642744
688 406077048568871060
689 419903108211736086
690 434189777106618089
691 448951928675039898
692 464205188159786771
693 479965395144263560
694 496249183083016592
695 513073419366608194
696 530455809347340568
697 548414313023256074
698 566967775250598105
699 586135318138668098
700 605936997844119006
701 626393171678361020
702 647525183304044800
703 669354703576436100
704 691904444580694774
705 715197473131277672
706 739257955610125676
707 764110443069200024
708 789780647355563705
709 816294696659097664
710 843679945033986301
711 871964197254364480
712 901176552271559154
713 931346596130875980
714 962505281634268131
715 994684088093983856
716 1027915937797702704
717 1062234321256530118
718 1097674252915815910
719 1134271360578975574
720 1172062881023840083
721 1211086712158602028
722 1251382451172554607
723 1292990408004061050
724 1335952686755916809
725 1380312158922274442
726 1426113590896479509
727 1473402575429520120
728 1522226706036725030
729 1572634465016952072
730 1624676447801507198
731 1678404205890596266
732 1733871522033751561
733 1791133206288363710
734 1850246425305526089
735 1911269449742326612
736 1974263038634898781
737 2039289136235030552
738 2106412314991578075
739 2175698419911113176
740 2247216071229643228
741 2321035254223605152
742 2397228885360551300
743 2475871345517859100
744 2557040110803325182
745 2640814226955435314
746 2727276008908882559
747 2816509454180805230
748 2908602012493363270
749 3003642935755579600
750 3101725122125069696
751 3202943400228303092
752 3307396449104905617
753 3415185014099769820
754 3526413907404128707
755 3641190153088288754
756 3759625069825753089
757 3881832342313873218
758 4007930191250793280
759 4138039368426129214
760 4272285415695356760
761 4410796580787652268
762 4553706170728957887
763 4701150385451928490
764 4853270767583904267
765 5010211950691706536
766 5172124211298001986
767 5339161128633992144
768 5511482240987110210
769 5689250613567931348
770 5872635605494324685
771 6061810342418685868
772 6256954596457882484
773 6458252159944172710
774 6665893845079882436
775 6880074755218612184
776 7100997406777756590
777 7328868894153491804
778 7563904141182001905
779 7806322955837887840
780 8056353414020646873
781 8314228799865811530
782 8580191129696089474
783 8854487973820224690
784 9137376123693826131
785 9429118290741539014
786 9729986925155730308
787 10040260787327294400
788 10360228921618412875
789 10690187095624034526
790 11030441937982668533
791 11381307240743781366
792 11743108264869573657
793 12116177900599769580
794 12500861150389979110
795 12897511142218253202
796 13306493793961625793
797 13728183674182576164
798 14162968858421089445
799 14611246632056883960
800 15073428542896824510
801 15549935940274515790
802 16041205235200474107
803 16547683269922611740
804 17069832790430380543
805 17608127640241325532
806 18163058457373911347
807 18735127686187259280
808 19324855504065944950
809 19932774644655205208
810 20559436567282395286
811 21205406084997730256
812 21871267782466268441
813 22557620441706829270
814 23265083722461386097
815 23994292378597796856
816 24745903207224001688
817 25520589048174443938
818 26319046016929909590
819 27141987279681087034
820 27990150576906917858
821 28864291765932121258
822 29765192651357073748
823 30693654287106915780
824 31650505121201318584
825 32636594048678273888
826 33652798888118770302
827 34700019176915768036
828 35779184987733256870
829 36891249456943464612
830 38037197959747096560
831 39218040362690748042
832 40434820566385270570
833 41688608472331986730
834 42980509913375784935
835 44311658325166758496
836 45683225074107358451
837 47096410823049092178
838 48552456278391776700
839 50052633239721512112
840 51598255776715727211
841 53190670951663481780
842 54831270449468500529
843 56521480962102451000
844 58262776283338883908
845 60056667343383681672
846 61904714793388953611
847 63808518678626138486
848 65769731525476168670
849 67790047640654216160
850 69871216727621321759
851 72015032799502360484
852 74223348338771941279
853 76498062810607021940
854 78841137394829792776
855 81254583086574263210
856 83740476015604072489
857 86300945120224980928
858 88938188085151960075
859 91654458574752711352
860 94452082805956185448
861 97333446325908156598
862 100301011253460950072
863 103357302586490437880
864 106504926129953700231
865 109746554317063111696
866 113084944859995046789
867 116522926069293814470
868 120063416246851956655
869 123709408486809865978
870 127463990849627626034
871 131330330627943560094
872 135311695323133243217
873 139411436358419486940
874 143633010899692913159
875 147979964998383847502
876 152455956279870804629
877 157064736497398634312
878 161810175133027578440
879 166696241344113829422
880 171727028502234857315
881 176906735512463044476
882 182239692338641921482
883 187730340675942679160
884 193383260490219269101
885 199203150022981453752
886 205194853396898016061
887 211363339932607286070
888 217713732850589913280
889 224251287877820612070
890 230981423102056773220
891 237909696846643733340
892 245041838710163558705
893 252383726686224156980
894 259941419448798547652
895 267721132694173757916
896 275729272707884614694
897 283972411904439228880
898 292457323740804354910
899 301190957429908654080
900 310180474239803588206
901 319433221355320971052
902 328956769632849641411
903 338758886584940184360
904 348847575633336123254
905 359231048189624685156
906 369917764481833816283
907 380916404704694833094
908 392235911466265417685
909 403885459979593901856
910 415874502210481776796
911 428212736082859925232
912 440910151378308779192
913 453976997925612200200
914 467423833339402177313
915 481261490164923853788
916 495501125510960259682
917 510154187118925900264
918 525232464984182124845
919 540748056319213856134
920 556713419223425517501
921 573141336508154503248
922 590044971516346076707
923 607437830777868570670
924 625333822044527016173
925 643747215742075903444
926 662692705329829125769
927 682185367516546284370
928 702240725015957175285
929 722874705491558079088
930 744103706825789061446
931 765944554759652178188
932 788414570753232530801
933 811531528283827334210
934 835313723424717148315
935 859779929766473037340
936 884949471798605116765
937 910842178416428698924
938 937478459242390140880
939 964879256681950112056
940 993066125276779992913
941 1022061182270770620430
942 1051887190142581308486
943 1082567505644090796660
944 1114126165612724401095
945 1146587834442237964528
946 1179977893333858267394
947 1214322386160641356936
948 1249648112266813498715
949 1285982570684468462468
950 1323354056652619095345
951 1361791604146489755160
952 1401325086235440294438
953 1441985155882584470440
954 1483803350326574115847
955 1526812030110946264642
956 1571044487619567000890
957 1616534884292525447220
958 1663318363514807767395
959 1711430985977424485648
960 1760909847060696620851
961 1811793010296690242524
962 1864119629462442068268
963 1917929880101842759850
964 1973265086482815962895
965 2030167651134158147942
966 2088681186899031916168
967 2148850444444585409344
968 2210721449579524710275
969 2274341428691672994100
970 2339758951580421630704
971 2407023854779975147680
972 2476187390089420760839
973 2547302145736753260930
974 2620422200877298470518
975 2695603044556477540462
976 2772901736375655302146
977 2852376823208974850472
978 2934088506328930918935
979 3018098555835810516464
980 3104470484459844192883
981 3193269459659180679018
982 3284562484414270492715
983 3378418306953879467200
984 3474907608777925904474
985 3574102911968501486654
986 3676078774782083393145
987 3780911696506497406120
988 3888680320879848706730
989 3999465338451918604768
990 4113349698198082772319
991 4230418507348063906588
992 4350759251475185022052
993 4474461691753054683700
994 4601618093918055530301
995 4732323122919479523794
996 4866674081060660138867
997 5004770800005892833262
998 5146715888530188771785
999 5292614621851795875146
1000 5442575199323313459779