1 0
2 1
3 1
4 1
5 1
6 1
7 2
8 2
9 3
10 3
11 4
12 4
13 5
14 5
15 7
16 7
17 9
18 10
19 12
20 13
21 16
22 17
23 20
24 22
25 25
26 28
27 32
28 35
29 40
30 45
31 50
32 56
33 63
34 70
35 78
36 87
37 96
38 107
39 118
40 131
41 144
42 160
43 175
44 194
45 213
46 235
47 257
48 284
49 310
50 342
51 373
52 410
53 447
54 491
55 534
56 585
57 637
58 696
59 756
60 826
61 896
62 977
63 1060
64 1153
65 1250
66 1359
67 1471
68 1597
69 1729
70 1874
71 2026
72 2195
73 2371
74 2565
75 2770
76 2992
77 3229
78 3486
79 3757
80 4052
81 4366
82 4703
83 5063
84 5451
85 5863
86 6306
87 6780
88 7285
89 7827
90 8406
91 9023
92 9683
93 10390
94 11140
95 11945
96 12801
97 13716
98 14689
99 15731
100 16835
101 18018
102 19273
103 20613
104 22035
105 23557
106 25165
107 26887
108 28710
109 30655
110 32715
111 34915
112 37240
113 39723
114 42349
115 45147
116 48107
117 51263
118 54595
119 58147
120 61901
121 65894
122 70115
123 74606
124 79347
125 84390
126 89717
127 95373
128 101349
129 107695
130 114392
131 121501
132 129008
133 136965
134 145367
135 154274
136 163670
137 173627
138 184135
139 195256
140 206994
141 219415
142 232515
143 246373
144 260992
145 276441
146 292737
147 309958
148 328111
149 347287
150 367505
151 388843
152 411339
153 435079
154 460092
155 486481
156 514287
157 543600
158 574484
159 607038
160 641319
161 677443
162 715484
163 755545
164 797726
165 842141
166 888883
167 938089
168 989872
169 1044353
170 1101679
171 1161984
172 1225410
173 1292116
174 1362269
175 1436016
176 1513559
177 1595063
178 1680729
179 1770751
180 1865361
181 1964738
182 2069162
183 2178833
184 2294030
185 2414991
186 2542030
187 2675378
188 2815400
189 2962353
190 3116610
191 3278471
192 3448353
193 3626550
194 3813542
195 4009660
196 4215392
197 4431123
198 4657397
199 4894598
200 5143344
201 5404063
202 5677393
203 5963830
204 6264073
205 6578629
206 6908284
207 7253605
208 7615404
209 7994329
210 8391274
211 8806906
212 9242223
213 9697966
214 10175174
215 10674692
216 11197650
217 11744932
218 12317793
219 12917212
220 13544500
221 14200759
222 14887422
223 15605647
224 16357012
225 17142800
226 17964664
227 18824046
228 19722740
229 20662269
230 21644611
231 22671442
232 23744841
233 24866678
234 26039210
235 27264424
236 28544790
237 29882493
238 31280141
239 32740156
240 34265365
241 35858346
242 37522193
243 39259731
244 41074228
245 42968808
246 44947009
247 47012167
248 49168139
249 51418570
250 53767554
251 56219098
252 58777632
253 61447438
254 64233341
255 67140013
256 70172573
257 73336148
258 76636275
259 80078437
260 83668654
261 87412889
262 91317554
263 95389167
264 99634652
265 104060991
266 108675701
267 113486366
268 118500995
269 123727855
270 129175602
271 134853086
272 140769693
273 146935019
274 153359079
275 160052315
276 167025531
277 174289916
278 181857176
279 189739418
280 197949148
281 206499506
282 215403989
283 224676673
284 234332158
285 244385663
286 254852796
287 265750049
288 277094248
289 288903061
290 301194683
291 313988182
292 327303023
293 341159834
294 355579592
295 370584397
296 386196898
297 402440930
298 419340734
299 436922055
300 455211002
301 474235149
302 494022674
303 514603277
304 536007121
305 558266252
306 581413136
307 605482095
308 630508130
309 656528174
310 683579712
311 711702538
312 740936977
313 771325642
314 802911971
315 835741787
316 869861597
317 905320734
318 942169202
319 980459809
320 1020246381
321 1061585653
322 1104535267
323 1149156237
324 1195510495
325 1243663351
326 1293681413
327 1345634802
328 1399594832
329 1455636851
330 1513837445
331 1574277235
332 1637038534
333 1702207842
334 1769873275
335 1840127711
336 1913065712
337 1988786643
338 2067392062
339 2148988509
340 2233684682
341 2321594887
342 2412835718
343 2507529424
344 2605801132
345 2707781856
346 2813605475
347 2923412464
348 3037346340
349 3155557297
350 3278199265
351 3405433101
352 3537423462
353 3674342713
354 3816367262
355 3963681353
356 4116474058
357 4274942614
358 4439289200
359 4609725030
360 4786466602
361 4969739612
362 5159775968
363 5356817152
364 5561111061
365 5772916157
366 5992497741
367 6220131920
368 6456102702
369 6700705367
370 6954243405
371 7217032676
372 7489397816
373 7771676144
374 8064214985
375 8367374917
376 8681526946
377 9007056599
378 9344360526
379 9693850306
380 10055950088
381 10431099627
382 10819751831
383 11222376643
384 11639458034
385 12071497561
386 12519012452
387 12982538375
388 13462627421
389 13959851758
390 14474801069
391 15008085793
392 15560335831
393 16132202856
394 16724358967
395 17337499934
396 17972343269
397 18629631057
398 19310129355
399 20014630038
400 20743950191
401 21498934889
402 22280456040
403 23089414663
404 23926741212
405 24793396784
406 25690373425
407 26618696365
408 27579423745
409 28573648302
410 29602498711
411 30667140087
412 31768775393
413 32908646969
414 34088037361
415 35308270278
416 36570713139
417 37876776793
418 39227918116
419 40625640844
420 42071497606
421 43567090078
422 45114072925
423 46714152595
424 48369091365
425 50080707324
426 51850877782
427 53681538609
428 55574689648
429 57532392620
430 59556776676
431 61650037537
432 63814442462
433 66052328632
434 68366110294
435 70758275652
436 73231394143
437 75788114695
438 78431172335
439 81163385704
440 83987666013
441 86907012926
442 89924523717
443 93043390602
444 96266909224
445 99598475213
446 103041595128
447 106599881391
448 110277063404
449 114076984053
450 118003610136
451 122061028051
452 126253456909
453 130585242458
454 135060870401
455 139684962082
456 144462287013
457 149397757798
458 154496445443
459 159763572507
460 165204528657
461 170824865665
462 176630312191
463 182626767982
464 188820321657
465 195217243073
466 201824001299
467 208647259124
468 215693890134
469 222970972461
470 230485809041
471 238245919480
472 246259060577
473 254533220452
474 263076638140
475 271897797048
476 281005447861
477 290408600138
478 300116545424
479 310138851409
480 320485384055
481 331166301069
482 342192077601
483 353573497825
484 365321680861
485 377448075197
486 389964483483
487 402883056458
488 416216321457
489 429977174453
490 444178908814
491 458835210460
492 473960185493
493 489568354872
494 505674685989
495 522294585563
496 539443931389
497 557139068758
498 575396840907
499 594234585172
500 613670167630
501 633721977426
502 654408961685
503 675750623703
504 697767056519
505 720478940984
506 743907583707
507 768074913511
508 793003519567
509 818716652162
510 845238259420
511 872592988127
512 900806225167
513 929904096744
514 959913510056
515 990862157373
516 1022778556146
517 1055692053433
518 1089632870938
519 1124632108049
520 1160721787177
521 1197934862066
522 1236305261596
523 1275867898681
524 1316658719348
525 1358714710427
526 1402073948892
527 1446775615572
528 1492860042798
529 1540368729025
530 1589344392149
531 1639830983102
532 1691873739606
533 1745519206304
534 1800815286846
535 1857811265364
536 1916557864538
537 1977107266387
538 2039513170784
539 2103830823598
540 2170117073542
541 2238430401976
542 2308830986299
543 2381380729331
544 2456143323341
545 2533184287560
546 2612571030505
547 2694372889777
548 2778661201356
549 2865509339354
550 2954992786169
551 3047189181221
552 3142178389568
553 3240042553354
554 3340866168033
555 3444736134292
556 3551741835288
557 3661975198595
558 3775530771959
559 3892505788665
560 4013000251613
561 4137116999524
562 4264961792499
563 4396643389262
564 4532273631472
565 4671967525101
566 4815843333761
567 4964022661689
568 5116630548844
569 5273795566133
570 5435649909599
571 5602329500531
572 5773974089701
573 5950727359599
574 6132737031043
575 6320154979030
576 6513137338733
577 6711844627242
578 6916441860553
579 7127098678332
580 7343989463930
581 7567293484093
582 7797195009017
583 8033883458932
584 8277553536397
585 8528405376803
586 8786644684417
587 9052482899615
588 9326137335509
589 9607831353241
590 9897794512320
591 10196262750814
592 10503478540525
593 10819691085552
594 11145156478963
595 11480137910852
596 11824905840202
597 12179738209164
598 12544920620825
599 12920746573954
600 13307517643336
601 13705543725393
602 14115143235752
603 14536643362388
604 14970380270557
605 15416699378637
606 15875955566808
607 16348513465722
608 16834747684416
609 17335043108146
610 17849795135399
611 18379410000856
612 18924305017839
613 19484908915928
614 20061662105225
615 20655017025065
616 21265438419244
617 21893403712772
618 22539403294315
619 23203940909985
620 23887533970475
621 24590713957954
622 25314026746697
623 26058033041087
624 26823308705727
625 27610445223124
626 28420050051691
627 29252747099211
628 30109177096964
629 30989998107869
630 31895885912847
631 32827534541543
632 33785656690524
633 34770984272479
634 35784268853894
635 36826282243026
636 37897816942807
637 38999686765008
638 40132727319186
639 41297796648782
640 42495775743367
641 43727569217883
642 44994105844061
643 46296339259680
644 47635248541085
645 49011838938236
646 50427142474881
647 51882218732092
648 53378155471793
649 54916069454936
650 56497107111917
651 58122445390914
652 59793292461266
653 61510888615967
654 63276507003614
655 65091454570864
656 66957072847661
657 68874738925189
658 70845866279945
659 72871905812565
660 74954346706467
661 77094717512518
662 79294587068678
663 81555565626028
664 83879305814242
665 86267503836087
666 88721900474278
667 91244282339014
668 93836482944214
669 96500384003416
670 99237916559969
671 102051062359870
672 104941855031575
673 107912381519701
674 110964783344160
675 114101258090331
676 117324060731219
677 120635505204604
678 124037965793992
679 127533878775992
680 131125743891812
681 134816126060255
682 138607656923169
683 142503036656454
684 146505035585166
685 150616496075456
686 154840334252904
687 159179541971058
688 163637188615807
689 168216423184840
690 172920476174208
691 177752661750862
692 182716379757238
693 187815117972670
694 193052454218254
695 198432058743926
696 203957696429659
697 209633229280004
698 215462618759852
699 221449928392315
700 227599326211048
701 233915087500369
702 240401597360737
703 247063353572443
704 253904969314733
705 260931176149546
706 268146826875671
707 275556898674163
708 283166496094406
709 290980854342013
710 299005342440330
711 307245466657379
712 315706873823975
713 324395354944097
714 333316848666908
715 342477445061262
716 351883389287716
717 361541085534470
718 371457100870284
719 381638169389080
720 392091196241851
721 402823261970119
722 413841626766325
723 425153734994010
724 436767219657208
725 448689907158131
726 460929821974163
727 473495191633238
728 486394451651225
729 499636250723532
730 513229455903699
731 527183158065184
732 541506677320742
733 556209568734596
734 571301628038981
735 586792897596434
736 602693672393976
737 619014506313559
738 635766218404593
739 652959899442602
740 670606918540734
741 688718929997247
742 707307880226946
743 726386014959607
744 745965886493070
745 766060361223330
746 786682627283993
747 807846202410184
748 829564941945582
749 851853047106693
750 874725073361083
751 898195939072805
752 922280934321437
753 946995729932467
754 972356386718862
755 998379364968140
756 1025081534111444
757 1052480182649115
758 1080593028322081
759 1109438228481407
760 1139034390744794
761 1169400583887017
762 1200556348988885
763 1232521710831216
764 1265317189616465
765 1298963812874438
766 1333483127740223
767 1368897213454567
768 1405228694207823
769 1442500752218858
770 1480737141231833
771 1519962200183994
772 1560200867340557
773 1601478694640902
774 1643821862483964
775 1687257194738632
776 1731812174272780
777 1777514958641699
778 1824394396347912
779 1872480043303956
780 1921802179839020
781 1972391827923693
782 2024280769024330
783 2077501562107021
784 2132087562328863
785 2188072939925811
786 2245492699760425
787 2304382701083916
788 2364779678049327
789 2426721260369188
790 2490245994786561
791 2555393366741032
792 2622203822821839
793 2690718793435794
794 2760980716360329
795 2833033060439797
796 2906920350233838
797 2982688190864726
798 3060383293790441
799 3140053502800068
800 3221747821039690
801 3305516438187654
802 3391410758733095
803 3479483430464021
804 3569788374033526
805 3662380812762857
806 3757317303634000
807 3854655768446085
808 3954455526238991
809 4056777325947554
810 4161683380298613
811 4269237399969942
812 4379504629111772
813 4492551881056386
814 4608447575474382
815 4727261775792482
816 4849066228034294
817 4973934399960171
818 5101941521756926
819 5233164626953750
820 5367682594978398
821 5505576194020672
822 5646928125514239
823 5791823068968732
824 5940347728556275
825 6092590879976646
826 6248643419173646
827 6408598411420641
828 6572551142236234
829 6740599168720048
830 6912842372863719
831 7089383015211882
832 7270325790603292
833 7455777884361999
834 7645849030549724
835 7840651570727567
836 8040300514933465
837 8244913603102740
838 8454611368816419
839 8669517203604509
840 8889757423560348
841 9115461336578612
842 9346761312070261
843 9583792851237926
844 9826694659949630
845 10075608722297829
846 10330680376742103
847 10592058393017740
848 10859895051804539
849 11134346225104304
850 11415571459509238
851 11703734060317796
852 11999001178530950
853 12301543898788485
854 12611537330375250
855 12929160699116555
856 13254597442484368
857 13588035305748677
858 13929666441332061
859 14279687509316970
860 14638299781359439
861 15005709245712390
862 15382126715808431
863 15767767940125545
864 16162853715610170
865 16567610002507221
866 16982268042965068
867 17407064481014756
868 17842241486489367
869 18288046880512088
870 18744734264927931
871 19212563153446083
872 19691799106960952
873 20182713870562065
874 20685585514902567
875 21200698579473698
876 21728344220247973
877 22268820359392286
878 22822431839601818
879 23389490580496321
880 23970315739833233
881 24565233877025370
882 25174579121494780
883 25798693343517452
884 26437926330177381
885 27092635963820079
886 27763188405828691
887 28449958283171004
888 29153328880297612
889 29873692334024594
890 30611449834062661
891 31367011826557495
892 32140798223511096
893 32933238615516545
894 33744772490414961
895 34575849455508843
896 35426929466017637
897 36298483057139105
898 37190991582609079
899 38104947457204921
900 39040854405803096
901 39999227716656207
902 40980594501572936
903 41985493960390645
904 43014477652633614
905 44068109773841145
906 45146967439153285
907 46251640971880133
908 47382734199708120
909 48540864755992515
910 49726664388998500
911 50940779276648362
912 52183870349310761
913 53456613618450323
914 54759700513734440
915 56093838226135508
916 57459750059834510
917 58858175790589511
918 60289872033021436
919 61755612614765947
920 63256188959997445
921 64792410479991051
922 66365104973439172
923 67975119034327802
924 69623318469712406
925 71310588725506406
926 73037835322667889
927 74805984301614069
928 76615982677457882
929 78468798904054704
930 80365423349048587
931 82306868778238359
932 84294170851493461
933 86328388628251848
934 88410605085040247
935 90541927643224745
936 92723488708998998
937 94956446224178038
938 97241984229835178
939 99581313441061735
940 101975671835097372
941 104426325251304400
942 106934568004773419
943 109501723512418500
944 112129144933374131
945 114818215822260601
946 117570350797339687
947 120386996222342623
948 123269630903499726
949 126219766800968758
950 129238949756207212
951 132328760234190834
952 135490814082236557
953 138726763304564881
954 142038296853838600
955 145427141439256156
956 148895062352444547
957 152443864310434273
958 156075392317172527
959 159791532543113132
960 163594213223785847
961 167485405577356361
962 171467124742081691
963 175541430733370651
964 179710429421570212
965 183976273530463449
966 188341163657013223
967 192807349312843144
968 197377129987982929
969 202052856237066155
970 206836930788725126
971 211731809678668120
972 216740003406566761
973 221864078117773623
974 227106656809986188
975 232470420565568287
976 237958109809866236
977 243572525596552220
978 249316530919678816
979 255193052054047018
980 261205079923553781
981 267355671498805947
982 273647951223894753
983 280085112473958664
984 286670419042744885
985 293407206662399035
986 300298884554669444
987 307348937015436043
988 314560925031982443
989 321938487935286944
990 329485345086032016
991 337205297597242879
992 345102230092229899
993 353180112500414987
994 361443001889959367
995 369895044340159983
996 378540476851779133
997 387383629298945633
998 396428926420761505
999 405680889855916019
1000 415144140218692826