0 1
1 1
2 0
3 1
4 1
5 1
6 1
7 2
8 3
9 2
10 3
11 3
12 4
13 4
14 4
15 6
16 7
17 7
18 7
19 9
20 10
21 12
22 13
23 14
24 17
25 18
26 19
27 22
28 26
29 28
30 29
31 34
32 38
33 41
34 44
35 50
36 57
37 60
38 65
39 72
40 81
41 86
42 94
43 105
44 114
45 124
46 133
47 146
48 161
49 174
50 187
51 204
52 224
53 240
54 258
55 282
56 309
57 332
58 354
59 386
60 419
61 450
62 481
63 524
64 569
65 606
66 651
67 703
68 759
69 812
70 871
71 940
72 1011
73 1082
74 1154
75 1243
76 1336
77 1428
78 1526
79 1636
80 1757
81 1873
82 1998
83 2140
84 2296
85 2448
86 2603
87 2788
88 2981
89 3172
90 3376
91 3610
92 3855
93 4096
94 4358
95 4646
96 4956
97 5264
98 5594
99 5962
100 6344
101 6736
102 7148
103 7606
104 8087
105 8582
106 9103
107 9666
108 10272
109 10884
110 11531
111 12240
112 12994
113 13759
114 14560
115 15444
116 16367
117 17319
118 18320
119 19410
120 20561
121 21730
122 22972
123 24310
124 25723
125 27172
126 28708
127 30360
128 32086
129 33878
130 35757
131 37777
132 39902
133 42104
134 44413
135 46878
136 49484
137 52164
138 54990
139 58006
140 61182
141 64468
142 67904
143 71582
144 75439
145 79436
146 83626
147 88100
148 92791
149 97632
150 102736
151 108144
152 113821
153 119706
154 125890
155 132440
156 139294
157 146424
158 153882
159 161790
160 170073
161 178678
162 187694
163 197206
164 207187
165 217544
166 228396
167 239844
168 251853
169 264316
170 277336
171 291099
172 305484
173 320434
174 336075
175 352568
176 369810
177 387704
178 406448
179 426148
180 446763
181 468180
182 490581
183 514132
184 538717
185 564294
186 591009
187 619078
188 648388
189 678884
190 710728
191 744108
192 779011
193 815267
194 853128
195 892830
196 934296
197 977384
198 1022328
199 1069460
200 1118613
201 1169724
202 1223040
203 1278884
204 1337136
205 1397644
206 1460787
207 1526840
208 1595733
209 1667314
210 1741984
211 1820056
212 1901386
213 1985968
214 2074090
215 2166194
216 2262172
217 2361934
218 2465855
219 2574366
220 2687453
221 2804916
222 2927285
223 3055020
224 3188067
225 3326286
226 3470148
227 3620308
228 3776607
229 3938985
230 4107979
231 4284278
232 4467742
233 4658222
234 4856511
235 5063174
236 5278200
237 5501500
238 5733831
239 5975890
240 6227612
241 6489045
242 6760873
243 7044034
244 7338448
245 7644136
246 7961947
247 8292756
248 8636709
249 8993694
250 9364765
251 9750916
252 10152288
253 10568820
254 11001548
255 11451838
256 11919618
257 12405020
258 12909270
259 13433726
260 13978440
261 14543500
262 15130441
263 15740556
264 16374169
265 17031382
266 17713814
267 18423037
268 19159232
269 19922840
270 20715452
271 21538952
272 22393633
273 23279966
274 24199763
275 25154956
276 26146257
277 27173920
278 28240180
279 29347272
280 30495863
281 31686406
282 32921266
283 34203172
284 35532638
285 36910550
286 38339492
287 39822376
288 41360039
289 42953242
290 44605240
291 46319002
292 48095718
293 49936392
294 51844544
295 53823548
296 55874604
297 57999348
298 60201286
299 62484465
300 64850432
301 67300876
302 69839851
303 72471700
304 75198573
305 78022086
306 80947154
307 83978572
308 87118690
309 90369672
310 93736633
311 97225388
312 100838340
313 104578268
314 108450964
315 112462796
316 116616653
317 120915516
318 125366412
319 129975882
320 134747701
321 139685476
322 144796748
323 150089033
324 155566458
325 161233664
326 167098577
327 173170082
328 179452924
329 185952240
330 192677204
331 199637268
332 206838512
333 214286444
334 221991612
335 229964676
336 238212486
337 246741484
338 255563130
339 264690056
340 274129405
341 283889134
342 293982208
343 304422338
344 315218027
345 326378088
346 337917588
347 349851212
348 362189351
349 374942080
350 388125950
351 401757770
352 415848829
353 430411437
354 445463529
355 461024300
356 477106776
357 493724844
358 510898673
359 528649258
360 546992426
361 565943086
362 585524450
363 605760206
364 626667856
365 648264796
366 670576558
367 693630330
368 717445255
369 742041936
370 767448878
371 793696096
372 820805864
373 848800888
374 877713993
375 907577980
376 938418706
377 970262112
378 1003144646
379 1037103138
380 1072166338
381 1108364916
382 1145738414
383 1184328810
384 1224169002
385 1265293090
386 1307745728
387 1351573296
388 1396813965
389 1443505384
390 1491698440
391 1541444870
392 1592787428
393 1645769328
394 1700446502
395 1756877982
396 1815111137
397 1875195564
398 1937193907
399 2001171748
400 2067182876
401 2135282554
402 2205542274
403 2278033784
404 2352818838
405 2429960224
406 2509536924
407 2591629612
408 2676307302
409 2763641950
410 2853720499
411 2946634258
412 3042460914
413 3141281048
414 3243192433
415 3348295804
416 3456680248
417 3568435277
418 3683670927
419 3802499814
420 3925021758
421 4051337856
422 4181569920
423 4315845476
424 4454274944
425 4596973330
426 4744076988
427 4895727110
428 5052048525
429 5213169692
430 5379244136
431 5550427688
432 5726862177
433 5908691768
434 6096086960
435 6289222444
436 6488255910
437 6693351216
438 6904696868
439 7122488684
440 7346903894
441 7578125718
442 7816364683
443 8061837808
444 8314746130
445 8575292816
446 8843714035
447 9120252104
448 9405131031
449 9698579310
450 10000859034
451 10312241919
452 10632976784
453 10963321566
454 11303567983
455 11654017704
456 12014950445
457 12386653000
458 12769452695
459 13163683388
460 13569659391
461 13987701944
462 14418174624
463 14861449538
464 15317876627
465 15787817948
466 16271675276
467 16769864631
468 17282777734
469 17810817640
470 18354432375
471 18914083390
472 19490210538
473 20083261442
474 20693736893
475 21322149894
476 21968990352
477 22634759480
478 23320011793
479 24025320686
480 24751230427
481 25498301996
482 26267152274
483 27058417634
484 27872705755
485 28710640508
486 29572910983
487 30460220732
488 31373249759
489 32312694282
490 33279317982
491 34273903714
492 35297207528
493 36350008148
494 37433150566
495 38547507212
496 39693920041
497 40873254920
498 42086451927
499 43334476796
500 44618270687
501 45938794592
502 47297094157
503 48694241808
504 50131283794
505 51609290274
506 53129419400
507 54692865544
508 56300788139
509 57954380730
510 59654929092
511 61403755736
512 63202151552
513 65051441482
514 66953055210
515 68908455438
516 70919080674
517 72986403348
518 75112006873
519 77297515088
520 79544522755
521 81854670324
522 84229709264
523 86671442035
524 89181640394
525 91762124768
526 94414836996
527 97141771440
528 99944900527
529 102826239660
530 105787943978
531 108832223808
532 111961265070
533 115177306312
534 118482731773
535 121879993644
536 125371512013
537 128959774516
538 132647420878
539 136437163722
540 140331689381
541 144333752064
542 148446279368
543 152672268988
544 157014702102
545 161476632336
546 166061297638
547 170772016156
548 175612087826
549 180584902952
550 185694036986
551 190943165060
552 196335943987
553 201876125410
554 207567666222
555 213414627458
556 219421063811
557 225591123512
558 231929187083
559 238439744020
560 245127280045
561 251996389899
562 259051910556
563 266298811084
564 273742049484
565 281386714097
566 289238150940
567 297301848434
568 305583292740
569 314088107846
570 322822208067
571 331791648138
572 341002500514
573 350460985796
574 360173631648
575 370147127726
576 380388183040
577 390903680476
578 401700820465
579 412786995516
580 424169619550
581 435856295352
582 447854974980
583 460173811736
584 472821004828
585 485804945942
586 499134415818
587 512818412460
588 526865988466
589 541286413196
590 556089368831
591 571284791674
592 586882666655
593 602893234096
594 619327175256
595 636195443416
596 653509062897
597 671279330868
598 689518033463
599 708237238824
600 727449119459
601 747166139464
602 767401287892
603 788167872208
604 809479311752
605 831349364996
606 853792338518
607 876822903556
608 900455859580
609 924706374240
610 949590213250
611 975123533898
612 1001322663336
613 1028204309880
614 1055785848259
615 1084085077294
616 1113119984750
617 1142908987998
618 1173471215166
619 1204826275592
620 1236993977039
621 1269994620292
622 1303849264283
623 1338579491820
624 1374207126251
625 1410754517522
626 1448244857691
627 1486701890376
628 1526149654076
629 1566612759940
630 1608116724508
631 1650687676536
632 1694352071076
633 1739137014236
634 1785070563343
635 1832181471594
636 1880498856904
637 1930052541612
638 1980873390021
639 2032993017172
640 2086443472242
641 2141257552177
642 2197469207085
643 2255113197542
644 2314224770254
645 2374840005240
646 2436996213095
647 2500731619324
648 2566084970674
649 2633095949696
650 2701805564628
651 2772255819138
652 2844489313796
653 2918549662620
654 2994481942065
655 3072332284498
656 3152147523862
657 3233975596088
658 3317866009298
659 3403869443544
660 3492037351106
661 3582422415776
662 3675078993997
663 3770062756054
664 3867430222720
665 3967239257558
666 4069549551749
667 4174422213196
668 4281919333565
669 4392104441944
670 4505043074217
671 4620802308432
672 4739450312817
673 4861056840170
674 4985693803094
675 5113434834276
676 5244354740207
677 5378530098448
678 5516039816603
679 5656964669506
680 5801386758877
681 5949390106774
682 6101061289858
683 6256488890353
684 6415763003366
685 6578975808160
686 6746222245494
687 6917599468184
688 7093206283849
689 7273143818778
690 7457516153195
691 7646429818010
692 7839993170280
693 8038317093744
694 8241515687300
695 8449705710366
696 8663005986445
697 8881538051920
698 9105426972976
699 9334800710504
700 9569789493570
701 9810526540236
702 10057148874684
703 10309796718984
704 10568612760713
705 10833742998704
706 11105337538916
707 11383549971336
708 11668536634490
709 11960457455180
710 12259476860637
711 12565763035028
712 12879487237924
713 13200824636782
714 13529955269072
715 13867063290540
716 14212336228542
717 14565965926948
718 14928149451922
719 15299088418022
720 15678988143186
721 16068058638456
722 16466515606808
723 16874579690180
724 17292475653892
725 17720433335192
726 18158688798004
727 18607483471924
728 19067063316533
729 19537679854702
730 20019591328176
731 20513061888796
732 21018360615836
733 21535762708102
734 22065550637466
735 22608013309792
736 23163445070349
737 23732146914904
738 24314427786225
739 24910603573182
740 25520996206531
741 26145934854660
742 26785757282111
743 27440808861340
744 28111441571522
745 28798015336490
746 29500899342545
747 30220471134290
748 30957115481398
749 31711225804504
750 32483205603613
751 33273467447468
752 34082431900790
753 34910528890762
754 35758199335688
755 36625894019900
756 37514072481706
757 38423204488904
758 39353771699985
759 40306266592764
760 41281191157622
761 42279058607844
762 43300395034062
763 44345738285412
764 45415636674708
765 46510650707608
766 47631354918209
767 48778336574046
768 49952194480291
769 51153540690478
770 52383002459828
771 53641220949723
772 54928849902344
773 56246557570520
774 57595028612469
775 58974962897488
776 60387074042066
777 61832091445304
778 63310762328449
779 64823850434650
780 66372134627209
781 67956410853492
782 69577494478403
783 71236218825884
784 72933433719630
785 74670007627588
786 76446830033872
787 78264810039896
788 80124874692904
789 82027971423935
790 83975070414268
791 85967163172846
792 88005260863962
793 90090396773200
794 92223628952307
795 94406038557084
796 96638728294304
797 98922824914212
798 101259481999125
799 103649878296806
800 106095216040912
801 108596723716430
802 111155658783762
803 113773306177012
804 116450976435188
805 119190008609316
806 121991773221016
807 124857670614418
808 127789129159511
809 130787608123766
810 133854601002597
811 136991633664876
812 140200262527790
813 143482077656312
814 146838706150250
815 150271810411864
816 153783086037721
817 157374265297983
818 161047120579992
819 164803462609780
820 168645138340173
821 172574034529144
822 176592081533688
823 180701251229196
824 184903555095968
825 189201047832458
826 193595831346276
827 198090052717032
828 202685902111086
829 207385616753952
830 212191484908024
831 217105844032226
832 222131078456792
833 227269623604870
834 232523970272874
835 237896662603778
836 243390295909774
837 249007520856616
838 254751048227905
839 260623646700300
840 266628140618123
841 272767414482876
842 279044417871398
843 285462163351432
844 292023723904019
845 298732237973602
846 305590914464611
847 312603030605456
848 319771929430333
849 327101024963792
850 334593807684927
851 342253842077584
852 350084764353844
853 358090287710056
854 366274208127805
855 374640401974380
856 383192823516251
857 391935510719572
858 400872591053480
859 410008279343142
860 419346875059238
861 428892768449348
862 438650446751395
863 448624491894660
864 458819577969437
865 469240477345890
866 479892067602369
867 490779328973646
868 501907341774068
869 513281293009552
870 524906483520112
871 536788325621496
872 548932340174852
873 561344163925060
874 574029556787738
875 586994399515610
876 600244690845522
877 613786555051940
878 627626249938741
879 641770164120702
880 656224814492316
881 670996853996538
882 686093080075454
883 701520432035340
884 717285988357394
885 733396975185264
886 749860774831330
887 766684923568472
888 783877108669964
889 801445177367824
890 819397146017804
891 837741197711204
892 856485679572483
893 875639111851352
894 895210198024749
895 915207822131588
896 935641046132157
897 956519119665636
898 977851490493966
899 999647802201774
900 1021917891137617
901 1044671797153782
902 1067919774394380
903 1091672289054494
904 1115940016461515
905 1140733852255080
906 1166064924121262
907 1191944589118652
908 1218384431305385
909 1245396273257312
910 1272992188461871
911 1301184498901898
912 1329985772520371
913 1359408835728247
914 1389466786066979
915 1420172990361113
916 1451541081909248
917 1483584973782840
918 1516318872390643
919 1549757275479192
920 1583914969813568
921 1618807044731762
922 1654448906994600
923 1690856278616338
924 1728045194678478
925 1766032017835256
926 1804833453814949
927 1844466549769664
928 1884948691652273
929 1926297620180824
930 1968531446883742
931 2011668652611326
932 2055728085291752
933 2100728976562564
934 2146690959133812
935 2193634064978648
936 2241578723844477
937 2290545780457048
938 2340556512978470
939 2391632631601234
940 2443796276972570
941 2497070038911200
942 2551476975340504
943 2607040611714958
944 2663784939345953
945 2721734435252596
946 2780914082401993
947 2841349369198180
948 2903066288527487
949 2966091358121600
950 3030451642710383
951 3096174753424312
952 3163288847152537
953 3231822648418658
954 3301805472532172
955 3373267225791302
956 3446238404592456
957 3520750119314148
958 3596834118368818
959 3674522788916896
960 3753849156594733
961 3834846910465680
962 3917550429091916
963 4001994781009269
964 4088215725586750
965 4176249739087052
966 4266134042328115
967 4357906601871288
968 4451606131122517
969 4547272118516042
970 4644944856057713
971 4744665441907910
972 4846475781563500
973 4950418617750516
974 5056537561036251
975 5164877092710680
976 5275482567107831
977 5388400242605692
978 5503677314911680
979 5621361920101600
980 5741503137753774
981 5864151024141456
982 5989356647108961
983 6117172090550872
984 6247650457501370
985 6380845906186484
986 6516813686562176
987 6655610145704924
988 6797292731989939
989 6941920033032148
990 7089551815098263
991 7240249028551398
992 7394073813938648
993 7551089541704494
994 7711360854020586
995 7874953671646462
996 8041935200661490
997 8212373975274856
998 8386339901390955
999 8563904265566222
1000 8745139742250672