0 1
1 1
2 0
3 1
4 2
5 2
6 2
7 3
8 4
9 5
10 6
11 7
12 9
13 11
14 13
15 16
16 19
17 22
18 27
19 32
20 37
21 44
22 52
23 60
24 70
25 82
26 95
27 110
28 127
29 146
30 169
31 194
32 221
33 254
34 291
35 331
36 377
37 429
38 487
39 553
40 626
41 707
42 800
43 903
44 1016
45 1145
46 1288
47 1445
48 1622
49 1819
50 2036
51 2278
52 2546
53 2842
54 3172
55 3536
56 3936
57 4381
58 4872
59 5411
60 6008
61 6665
62 7386
63 8183
64 9058
65 10017
66 11074
67 12233
68 13502
69 14897
70 16425
71 18095
72 19927
73 21931
74 24119
75 26515
76 29131
77 31984
78 35103
79 38504
80 42209
81 46252
82 50655
83 55446
84 60667
85 66346
86 72517
87 79232
88 86529
89 94450
90 103057
91 112398
92 122528
93 133522
94 145440
95 158352
96 172348
97 187504
98 203908
99 221670
100 240885
101 261660
102 284131
103 308418
104 334653
105 363000
106 393607
107 426640
108 462299
109 500766
110 542245
111 586978
112 635193
113 687140
114 743111
115 803388
116 868277
117 938133
118 1013301
119 1094157
120 1181131
121 1274643
122 1375153
123 1483183
124 1599247
125 1723903
126 1857780
127 2001507
128 2155764
129 2321309
130 2498906
131 2689379
132 2893644
133 3112629
134 3347330
135 3598851
136 3868314
137 4156925
138 4466012
139 4796931
140 5151138
141 5530225
142 5935830
143 6369709
144 6833772
145 7329990
146 7860472
147 8427512
148 9033480
149 9680906
150 10372536
151 11111214
152 11899976
153 12742104
154 13641006
155 14600317
156 15623954
157 16715997
158 17880792
159 19123011
160 20447528
161 21859529
162 23364582
163 24968503
164 26677474
165 28498121
166 30437370
167 32502583
168 34701638
169 37042775
170 39534746
171 42186901
172 45009036
173 48011545
174 51205514
175 54602569
176 58215035
177 62056047
178 66139387
179 70479655
180 75092393
181 79993913
182 85201495
183 90733511
184 96609249
185 102849131
186 109474847
187 116509184
188 123976251
189 131901632
190 140312211
191 149236416
192 158704397
193 168747840
194 179400233
195 190697064
196 202675635
197 215375358
198 228837967
199 243107330
200 258229779
201 274254340
202 291232557
203 309218844
204 328270739
205 348448740
206 369816685
207 392442046
208 416395761
209 441752654
210 468591768
211 496996198
212 527053568
213 558856392
214 592501920
215 628092664
216 665736800
217 705548046
218 747646226
219 792157722
220 839215380
221 888959130
222 941536503
223 997102554
224 1055820553
225 1117862566
226 1183409407
227 1252651420
228 1325789121
229 1403033188
230 1484605333
231 1570739024
232 1661679537
233 1757684912
234 1859026767
235 1965990414
236 2078875921
237 2197999044
238 2323691403
239 2456301662
240 2596196589
241 2743761314
242 2899400659
243 3063540318
244 3236627215
245 3419131004
246 3611545389
247 3814388615
248 4028205133
249 4253567097
250 4491074995
251 4741359505
252 5005083213
253 5282941385
254 5575664051
255 5884017953
256 6208807497
257 6550877111
258 6911113431
259 7290446471
260 7689852274
261 8110355385
262 8553030286
263 9019004359
264 9509460688
265 10025639787
266 10568842932
267 11140435349
268 11741848260
269 12374582635
270 13040212810
271 13740388905
272 14476841072
273 15251383581
274 16065917666
275 16922436323
276 17823028934
277 18769884637
278 19765297708
279 20811672803
280 21911528916
281 23067505437
282 24282368116
283 25559013657
284 26900476556
285 28309935865
286 29790720528
287 31346317122
288 32980377496
289 34696724966
290 36499363058
291 38392484154
292 40380476686
293 42467934982
294 44659669064
295 46960712958
296 49376335804
297 51912052980
298 54573635652
299 57367123318
300 60298836412
301 63375387289
302 66603694404
303 69990996559
304 73544865526
305 77273222059
306 81184352010
307 85286920831
308 89589991632
309 94103043411
310 98835987672
311 103799188801
312 109003484718
313 114460205855
314 120181198152
315 126178846431
316 132466096056
317 139056478921
318 145964139848
319 153203861303
320 160791092726
321 168741980361
322 177073395466
323 185802967361
324 194949117142
325 204531089811
326 214568991548
327 225083827821
328 236097539902
329 247633046911
330 259714288857
331 272366268129
332 285615096935
333 299488045861
334 314013590983
335 329221467355
336 345142723805
337 361809776415
338 379256468771
339 397518133785
340 416631654339
341 436635531155
342 457569952551
343 479476863115
344 502400040153
345 526385172346
346 551479937479
347 577734088572
348 605199542491
349 633930467882
350 663983382157
351 695417251308
352 728293589363
353 762676567508
354 798633126505
355 836233089070
356 875549282643
357 916657666002
358 959637456109
359 1004571266214
360 1051545248369
361 1100649236558
362 1151976902041
363 1205625913652
364 1261698099237
365 1320299620294
366 1381541152251
367 1445538066490
368 1512410626571
369 1582284190918
370 1655289417909
371 1731562486330
372 1811245323209
373 1894485834718
374 1981438153783
375 2072262896076
376 2167127419876
377 2266206104130
378 2369680635932
379 2477740302846
380 2590582305036
381 2708412078018
382 2831443621400
383 2959899849074
384 3094012951464
385 3234024765020
386 3380187165016
387 3532762472044
388 3692023867048
389 3858255831810
390 4031754604888
391 4212828647634
392 4401799138059
393 4599000481980
394 4804780836091
395 5019502661444
396 5243543296353
397 5477295543292
398 5721168288927
399 5975587146052
400 6240995111779
401 6517853261948
402 6806641470219
403 7107859145860
404 7422026011219
405 7749682906934
406 8091392618665
407 8447740747348
408 8819336610463
409 9206814168082
410 9610832996641
411 10032079297434
412 10471266933567
413 10929138519142
414 11406466547393
415 11904054551346
416 12422738321755
417 12963387168732
418 13526905220301
419 14114232783908
420 14726347756851
421 15364267078620
422 16029048252501
423 16721790921764
424 17443638493453
425 18195779838333
426 18979451051801
427 19795937268803
428 20646574562345
429 21532751910197
430 22455913222661
431 23417559462263
432 24419250839673
433 25462609078409
434 26549319780807
435 27681134879051
436 28859875163705
437 30087432923829
438 31365774681841
439 32696944015691
440 34083064503951
441 35526342776509
442 37029071663506
443 38593633479571
444 40222503425812
445 41918253102157
446 43683554168752
447 45521182138641
448 47434020294102
449 49425063767343
450 51497423767426
451 53654331945727
452 55899144942718
453 58235349097345
454 60666565311618
455 63196554115199
456 65829220910814
457 68568621393449
458 71418967189968
459 74384631699927
460 77470156130672
461 80680255775549
462 84019826515920
463 87493951540001
464 91107908330032
465 94867175898193
466 98777442264492
467 102844612230831
468 107074815431252
469 111474414652203
470 116050014479632
471 120808470252757
472 125756897318954
473 130902680649145
474 136253484793742
475 141817264174087
476 147602273771688
477 153617080195516
478 159870573122680
479 166371977178222
480 173130864234376
481 180157166125246
482 187461187846264
483 195053621218700
484 202945559016266
485 211148509626796
486 219674412229498
487 228535652486006
488 237745078821766
489 247316019278992
490 257262298940538
491 267598258005180
492 278338770496400
493 289499263604990
494 301095737750640
495 313144787345319
496 325663622260148
497 338670090085857
498 352182699170178
499 366220642435935
500 380803822074846
501 395952875101409
502 411689199772792
503 428034982974741
504 445013228559566
505 462647786644203
506 480963383974034
507 499985655340309
508 519741176061294
509 540257495639275
510 561563172583076
511 583687810408885
512 606662094938274
513 630517832884947
514 655287991746408
515 681006741126445
516 707709495482332
517 735432958316697
518 764215167947150
519 794095544850749
520 825114940607162
521 857315688581571
522 890741656347974
523 925438299880703
524 961452719664312
525 998833718726183
526 1037631862624368
527 1077899541550553
528 1119691034556304
529 1163062575940917
530 1208072423970810
531 1254780931943319
532 1303250621639541
533 1353546259346601
534 1405734934468083
535 1459886140773889
536 1516071860481517
537 1574366651193905
538 1634847735752147
539 1697595095208143
540 1762691564949101
541 1830222934040381
542 1900278048005697
543 1972948915083853
544 2048330816038079
545 2126522417751707
546 2207625890657853
547 2291747030089573
548 2378995381799803
549 2469484371708781
550 2563331439976581
551 2660658179667180
552 2761590480072821
553 2866258674808276
554 2974797694960473
555 3087347227374220
556 3204051878197159
557 3325061341989952
558 3450530576495257
559 3580619983204234
560 3715495594048417
561 3855329264325066
562 4000298872011871
563 4150588523822008
564 4306388768124539
565 4467896814904392
566 4635316763138437
567 4808859835731216
568 4988744622204313
569 5175197329544264
570 5368452041372593
571 5568750985654188
572 5776344811379473
573 5991492874405716
574 6214463532698863
575 6445534451443948
576 6684992918233977
577 6933136168606132
578 7190271722428341
579 7456717731373836
580 7732803337782321
581 8018869045449216
582 8315267102610959
583 8622361897457320
584 8940530366754545
585 9270162417880408
586 9611661364637975
587 9965444377477812
588 10331942948465673
589 10711603371402572
590 11104887237776390
591 11512271948922056
592 11934251244841146
593 12371335750413112
594 12824053539420098
595 13292950716883858
596 13778592020505090
597 14281561441676398
598 14802462866619142
599 15341920738498514
600 15900580741041588
601 16479110504265896
602 17078200333242270
603 17698563960474968
604 18340939322570338
605 19006089362192616
606 19694802855954426
607 20407895268982808
608 21146209637240256
609 21910617478320104
610 22702019731532649
611 23521347728450040
612 24369564194707799
613 25247664283961626
614 26156676645264635
615 27097664524748474
616 28071726902597641
617 29079999666687494
618 30123656823862775
619 31203911749946042
620 32322018479960585
621 33479273039647462
622 34677014819475433
623 35916627992751898
624 37199542979027991
625 38527237954115758
626 39901240408460407
627 41323128755185022
628 42794533989255267
629 44317141399654858
630 45892692336024627
631 47522986031354934
632 49209881482782893
633 50955299392094756
634 52761224167679837
635 54629705990161498
636 56562862943467683
637 58562883213258360
638 60632027355124043
639 62772630634496410
640 64987105440374447
641 67277943775486310
642 69647719825022801
643 72099092606248602
644 74634808701836719
645 77257705079274342
646 79970711998868401
647 82776856013441070
648 85679263062294935
649 88681161662219666
650 91785886198896179
651 94996880321531659
652 98317700443762919
653 101752019354472589
654 105303629941629689
655 108976449032481387
656 112774521354054919
657 116702023617384917
658 120763268729107961
659 124962710134726633
660 129304946297289239
661 133794725315471383
662 138436949685735039
663 143236681212671687
664 148199146071892679
665 153329740030547897
666 158634033829973305
667 164117778735241567
668 169786912257137001
669 175647564051486791
670 181706062001069911
671 187968938486104749
672 194442936848717666
673 201135018057100735
674 208052367575882854
675 215202402448628545
676 222592778598704218
677 230231398355604837
678 238126418213212948
679 246286256826810523
680 254719603256554220
681 263435425464494917
682 272442979072594378
683 281751816390120645
684 291371795718168028
685 301313090939442747
686 311586201402426404
687 322201962108387493
688 333171554210130930
689 344506515832393563
690 356218753223144320
691 368320552245495397
692 380824590220997504
693 393743948134435937
694 407092123210724242
695 420883041875608247
696 435131073111232622
697 449851042218135995
698 465058244996407986
699 480768462358080581
700 496997975383374058
701 513763580834641049
702 531082607141191862
703 548972930868767591
704 567452993688713098
705 586541819861240907
706 606259034247801074
707 626624880868922293
708 647660242023228940
709 669386657984009291
710 691826347291126150
711 715002227655405289
712 738937937493356154
713 763657858111564759
714 789187136559452432
715 815551709169862740
716 842778325808500336
717 870894574852610138
718 899928908920106896
719 929910671372009808
720 960870123610412976
721 992838473195103228
722 1025847902803668560
723 1059931600059330564
724 1095123788251681366
725 1131459757977327402
726 1168975899726851754
727 1207709737445524416
728 1247699963097106746
729 1288986472259531726
730 1331610400782332606
731 1375614162537712702
732 1421041488296613724
733 1467937465762309078
734 1516348580796182060
735 1566322759869844522
736 1617909413779007064
737 1671159482656764913
738 1726125482323494430
739 1782861552011907213
740 1841423503508186184
741 1901868871749701983
742 1964256966921262712
743 2028648928094359201
744 2095107778453494688
745 2163698482155249925
746 2234488002868387172
747 2307545364042981297
748 2382941710958243676
749 2460750374601513333
750 2541046937430636708
751 2623909301073762227
752 2709417756023549850
753 2797655053382612333
754 2888706478718950200
755 2982659928093290065
756 3079605986320133320
757 3179638007526417345
758 3282852198075024184
759 3389347701920362653
760 3499226688465503688
761 3612594442993881955
762 3729559459748670830
763 3850233537735362099
764 3974731879326832850
765 4103173191750387661
766 4235679791538874802
767 4372377712031958323
768 4513396814013956208
769 4658870899577470655
770 4808937829306264518
771 4963739642871305037
772 5123422683136932050
773 5288137723878596941
774 5458040101214243438
775 5633289848854671027
776 5814051837282993962
777 6000495916974105933
778 6192797065768581334
779 6391135540520523995
780 6595697033139857206
781 6806672831153344293
782 7024259982914036753
783 7248661467590034173
784 7480086370067535863
785 7718750060908919587
786 7964874381507998025
787 8218687834589021469
788 8480425780202123093
789 8750330637369572719
790 9028652091541967019
791 9315647308030014653
792 9611581151579521495
793 9916726412262313915
794 10231364037862805033
795 10555783372942155355
796 10890282404767515355
797 11235168016301271461
798 11590756246447790757
799 11957372557761135539
800 12335352111825150299
801 12725040052520259027
802 13126791797397759475
803 13540973337390865583
804 13967961545095084557
805 14408144491857470068
806 14861921773923333643
807 15329704847892766820
808 15811917375746826741
809 16308995579712902434
810 16821388607243019869
811 17349558906386936286
812 17893982611852207421
813 18455149942048163874
814 19033565607419469851
815 19629749230385984358
816 20244235777210959657
817 20877576002129041960
818 21530336904077352731
819 22203102196378861048
820 22896472789737430911
821 23611067288916569192
822 24347522503480501569
823 25106493972987178830
824 25888656507036353149
825 26694704740583189912
826 27525353704939724611
827 28381339414900972136
828 29263419472440608957
829 30172373687433935148
830 31109004715881349763
831 32074138716114545632
832 33068626023481431421
833 34093341844022420590
834 35149186967660638659
835 36237088501443492792
836 37358000623390872321
837 38512905357516178850
838 39702813370602452565
839 40928764791334975262
840 42191830052403760805
841 43493110756206684098
842 44833740564804498643
843 46214886114792215552
844 47637747957770036013
845 49103561527119012864
846 50613598131801138515
847 52169165977923760372
848 53771611218831804787
849 55422319034507226892
850 57122714741076903565
851 58874264931255489268
852 60678478646567221634
853 62536908582214184268
854 64451152325485696438
855 66422853628622619798
856 68453703717075753802
857 70545442634126652266
858 72699860622860104364
859 74918799546504917698
860 77204154348190947542
861 79557874551193171058
862 81981965800763167530
863 84478491448681980462
864 87049574181693302998
865 89697397695007822610
866 92424208412105664774
867 95232317252091123628
868 98124101445888275546
869 101102006402604860570
870 104168547627421529510
871 107326312692400677222
872 110577963261650759380
873 113926237172314367642
874 117373950572888394732
875 120924000120429399772
876 124579365238232548957
877 128343110435615723828
878 132218387691488505187
879 136208438903424134890
880 140316598403999175039
881 144546295546217297314
882 148901057359875409679
883 153384511280780608160
884 158000387954782034207
885 162752524118627139232
886 167644865559706092637
887 172681470156807834528
888 177866511004060635013
889 183204279620288525408
890 188699189246079214971
891 194355778230912730016
892 200178713512763112141
893 206172794192654585074
894 212342955206711833907
895 218694271098312087000
896 225231959893020961485
897 231961387079057243930
898 238888069696105152859
899 246017680535372501732
900 253356052453861758311
901 260909182805900117668
902 268683237995060603399
903 276684558149680580542
904 284919661925269383097
905 293395251437189133698
906 302118217327073458795
907 311095643966540795678
908 320334814801858330517
909 329843217843299993096
910 339628551303041107321
911 349698729385539143876
912 360061888234444699207
913 370726392040193729852
914 381700839312547002155
915 392994069322445252666
916 404615168717663792401
917 416573478316873913478
918 428878600086829464943
919 441540404307521184634
920 454569036930274345617
921 467974927133885428410
922 481768795084027417633
923 495961659901296347708
924 510564847843401743327
925 525590000707147887861
926 541049084456006702873
927 556954398079223677707
928 573318582688553770405
929 590154630858889703893
930 607475896219197192539
931 625296103300339174187
932 643629357646549156419
933 662490156197478241547
934 681893397947920922105
935 701854394892516243403
936 722388883262898694379
937 743513035064967689781
938 765243469924150499093
939 787597267246725590771
940 810591978705482893259
941 834245641058219055425
942 858576789307773356085
943 883604470212535617407
944 909348256156595833803
945 935828259388929431745
946 963065146641255189557
947 991080154134459240255
948 1019895102983720699275
949 1049532415012736313095
950 1080015128987717305158
951 1111366917282093014105
952 1143612102983137930462
953 1176775677452035361703
954 1210883318349173165114
955 1245961408136770672347
956 1282037053071254972870
957 1319138102698109310573
958 1357293169862243343332
959 1396531651247278172981
960 1436883748457467718042
961 1478380489656330077643
962 1521053751776431612262
963 1564936283315121045121
964 1610061727731389946778
965 1656464647459432896895
966 1704180548554863090186
967 1753245905989947223395
968 1803698189614650370942
969 1855575890800694056029
970 1908918549786269978778
971 1963766783739510921827
972 2020162315559265154150
973 2078148003432193435055
974 2137767871165701385134
975 2199067139316699530121
976 2262092257136692156456
977 2326890935354226968951
978 2393512179816254443942
979 2462006326010493371219
980 2532425074491469880410
981 2604821527233454345133
982 2679250224934109823974
983 2755767185293279425777
984 2834429942291940322330
985 2915297586496986168079
986 2998430806418159547370
987 3083891930944102893295
988 3171744972885178471446
989 3262055673651417459625
990 3354891549094654948956
991 3450321936544641553495
992 3548418043069685008448
993 3649252994993125650755
994 3752901888697739115986
995 3859441842750979475133
996 3968952051384784303694
997 4081513839364512325041
998 4197210718282465595570
999 4316128444312318556785
1000 4438355077461689565936