0 1
1 1
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 5
10 6
11 7
12 9
13 10
14 12
15 14
16 17
17 19
18 23
19 26
20 31
21 35
22 41
23 46
24 54
25 61
26 70
27 79
28 91
29 102
30 117
31 131
32 149
33 167
34 189
35 211
36 239
37 266
38 299
39 333
40 374
41 415
42 465
43 515
44 575
45 637
46 709
47 783
48 871
49 961
50 1065
51 1174
52 1299
53 1429
54 1579
55 1735
56 1913
57 2100
58 2311
59 2533
60 2785
61 3049
62 3345
63 3659
64 4010
65 4380
66 4794
67 5231
68 5717
69 6233
70 6804
71 7409
72 8080
73 8790
74 9573
75 10406
76 11322
77 12294
78 13363
79 14498
80 15742
81 17066
82 18512
83 20050
84 21732
85 23519
86 25466
87 27540
88 29796
89 32196
90 34806
91 37582
92 40594
93 43802
94 47276
95 50974
96 54979
97 59239
98 63843
99 68747
100 74040
101 79672
102 85749
103 92214
104 99180
105 106595
106 114573
107 123061
108 132193
109 141904
110 152337
111 163437
112 175351
113 188019
114 201611
115 216059
116 231545
117 248009
118 265639
119 284375
120 304433
121 325740
122 348527
123 372738
124 398613
125 426091
126 455446
127 486610
128 519878
129 555196
130 592872
131 632854
132 675492
133 720724
134 768926
135 820060
136 874520
137 932269
138 993752
139 1058930
140 1128282
141 1201792
142 1279966
143 1362800
144 1450863
145 1544145
146 1643259
147 1748235
148 1859723
149 1977764
150 2103085
151 2235735
152 2376499
153 2525470
154 2683483
155 2850658
156 3027926
157 3215417
158 3414139
159 3624287
160 3846936
161 4082314
162 4331616
163 4595102
164 4874066
165 5168844
166 5480820
167 5810390
168 6159090
169 6527357
170 6916854
171 7328129
172 7762967
173 8221992
174 8707179
175 9219227
176 9760277
177 10331164
178 10934191
179 11570313
180 12242071
181 12950519
182 13698416
183 14487007
184 15319265
185 16196588
186 17122250
187 18097808
188 19126818
189 20211076
190 21354418
191 22558864
192 23828633
193 25165957
194 26575419
195 28059577
196 29623383
197 31269686
198 33003926
199 34829259
200 36751595
201 38774504
202 40904379
203 43145200
204 45503978
205 47985097
206 50596176
207 53342158
208 56231292
209 59269053
210 62464475
211 65823597
212 69356239
213 73069154
214 76972981
215 81075195
216 85387435
217 89917918
218 94679295
219 99680730
220 104935934
221 110455009
222 116252940
223 122340836
224 128734984
225 135447703
226 142496649
227 149895397
228 157663227
229 165815024
230 174371737
231 183349841
232 192772053
233 202656472
234 213027880
235 223906118
236 235318108
237 247285728
238 259838176
239 272999466
240 286801421
241 301270312
242 316440703
243 332341516
244 349010233
245 366478527
246 384787216
247 403970936
248 424074008
249 445134455
250 467200332
251 490313245
252 514525489
253 539882486
254 566440997
255 594250815
256 623373474
257 653863362
258 685787392
259 719204906
260 754188500
261 790803088
262 829127353
263 869232144
264 911202959
265 955116990
266 1001066959
267 1049137208
268 1099428206
269 1152031869
270 1207057290
271 1264604548
272 1324791905
273 1387728528
274 1453542513
275 1522352734
276 1594298188
277 1669508159
278 1748133258
279 1830314358
280 1916214534
281 2005986996
282 2099808583
283 2197845811
284 2300290203
285 2407322949
286 2519151340
287 2635972286
288 2758010431
289 2885479566
290 3018622867
291 3157672750
292 3302892305
293 3454533847
294 3612882310
295 3778211452
296 3950829562
297 4131033908
298 4319157881
299 4515523961
300 4720492996
301 4934414559
302 5157678884
303 5390665244
304 5633795457
305 5887480582
306 6152176902
307 6428329720
308 6716432234
309 7016967099
310 7330467182
311 7657455224
312 7998507297
313 8354189234
314 8725123395
315 9111922601
316 9515258956
317 9935795636
318 10374258823
319 10831365903
320 11307901010
321 11804640429
322 12322430575
323 12862110965
324 13424595599
325 14010791946
326 14621686454
327 15258260402
328 15921578084
329 16612699919
330 17332774543
331 18082947508
332 18864457880
333 19678543433
334 20526540374
335 21409785460
336 22329720010
337 23287787125
338 24285540826
339 25324539357
340 26406457773
341 27532977786
342 28705905260
343 29927054632
344 31198372012
345 32521815236
346 33899480989
347 35333480988
348 36826074474
349 38379538393
350 39996306251
351 41678833431
352 43429740494
353 45251674149
354 47147456679
355 49119940279
356 51172163459
357 53307199971
358 55528320351
359 57838835988
360 60242267397
361 62742180967
362 65342365128
363 68046661086
364 70859144665
365 73783951616
366 76825467126
367 79988143048
368 83276696067
369 86695918243
370 90250881728
371 93946743277
372 97788957385
373 101783071890
374 105934950884
375 110250562910
376 114736211129
377 119398314799
378 124243648992
379 129279116257
380 134511997081
381 139949713355
382 145600087168
383 151471096800
384 157571146032
385 163908809347
386 170493113351
387 177333272920
388 184438981845
389 191820140687
390 199487159325
391 207450672963
392 215721858002
393 224312138032
394 233233510261
395 242498242330
396 252119211877
397 262109590337
398 272483197503
399 283254174286
400 294437348987
401 306047899919
402 318101736519
403 330615147703
404 343605199477
405 357089371145
406 371085966295
407 385613737815
408 400692315258
409 416341814226
410 432583282297
411 449438295065
412 466929416925
413 485079784772
414 503913587260
415 523455631418
416 543731842384
417 564768815374
418 586594332317
419 609236900258
420 632726288421
421 657093047960
422 682369072026
423 708587099466
424 735781293685
425 763986731454
426 793240004807
427 823578689522
428 855041972396
429 887670102172
430 921505038176
431 956589884950
432 992969566386
433 1030690238216
434 1069799990643
435 1110348241677
436 1152386463565
437 1195967558314
438 1241146612833
439 1287980250387
440 1336527417256
441 1386848713337
442 1439007205798
443 1493067740268
444 1549097786306
445 1607166722493
446 1667346717281
447 1729711991432
448 1794339728964
449 1861309318454
450 1930703299820
451 2002606577387
452 2077107405847
453 2154296578751
454 2234268448583
455 2317120092345
456 2402952371427
457 2491869066692
458 2583977982306
459 2679390054261
460 2778220492291
461 2880587863638
462 2986615279769
463 3096429447259
464 3210161903277
465 3327948037830
466 3449928372413
467 3576247555571
468 3707055691365
469 3842507299592
470 3982762699007
471 4127986936786
472 4278351220015
473 4434031816482
474 4595211542239
475 4762078624547
476 4934828250298
477 5113661396011
478 5298786430916
479 5490417916278
480 5688778270975
481 5894096530397
482 6106610080397
483 6326563381045
484 6554209761787
485 6789810112540
486 7033634749260
487 7285962062028
488 7547080456731
489 7817286965815
490 8096889259312
491 8386204221002
492 8685560038047
493 8995294731560
494 9315758331807
495 9647311369340
496 9990327128024
497 10345190099729
498 10712298325941
499 11092061804376
500 11484904926075
501 11891264840603
502 12311593981328
503 12746358392480
504 13196040353532
505 13661136655822
506 14142161334425
507 14639643901568
508 15154132177618
509 15686190484883
510 16236402590435
511 16805369847372
512 17393714257834
513 18002076569532
514 18631119451139
515 19281525548109
516 19954000783454
517 20649272359217
518 21368092192689
519 22111234872013
520 22879501218999
521 23673716203341
522 24494732647087
523 25343429083137
524 26220713611518
525 27127521711424
526 28064820241173
527 29033605208794
528 30034905931143
529 31069782747990
530 32139331352464
531 33244680458807
532 34386996294977
533 35567480229602
534 36787373444635
535 38047954505833
536 39350544227935
537 40696503199760
538 42087236833611
539 43524192851240
540 45008866536037
541 46542798163546
542 48127578471292
543 49764846045997
544 51456293001744
545 53203662330950
546 55008753812314
547 56873421308614
548 58799578919763
549 60789198240781
550 62844314751865
551 64967025044554
552 67159493471213
553 69423949321849
554 71762693751142
555 74178096920704
556 76672605194733
557 79248738256770
558 81909096599729
559 84656358599114
560 87493288316449
561 90422732545312
562 93447628920761
563 96571002948490
564 99795976447353
565 103125764543204
566 106563684466997
567 110113152531473
568 113777693276737
569 117560936441522
570 121466626487450
571 125498619546197
572 129660893346190
573 133957544155812
574 138392797106470
575 142971003145299
576 147696649787764
577 152574358061020
578 157608893713922
579 162805164173523
580 168168230206156
581 173703302902534
582 179415755827968
583 185311122017254
584 191395106643809
585 197673584049503
586 204152610929094
587 210838423412790
588 217737450806674
589 224856312709399
590 232201833343558
591 239781038734798
592 247601171630736
593 255669688762890
594 263994276399843
595 272582847674038
596 281443558806918
597 290584806532354
598 300015244993903
599 309743783288416
600 319779603085806
601 330132156275800
602 340811183354305
603 351826711209086
604 363189072273879
605 374908902480231
606 386997161237223
607 399465129533758
608 412324430791852
609 425587029159784
610 439265251244908
611 453371784629256
612 467919700544712
613 482922452597099
614 498393900439635
615 514348308751355
616 530800371917003
617 547765213296309
618 565258410982369
619 583295997350277
620 601894485955403
621 621070871413436
622 640842657453115
623 661227857170023
624 682245022312570
625 703913243901198
626 726252182819162
627 749282070856379
628 773023742623224
629 797498637068110
630 822728830804809
631 848737040099477
632 875546655690603
633 903181745312912
634 931667090036725
635 961028187385840
636 991291289296031
637 1022483405827613
638 1054632344834945
639 1087766716350688
640 1121915973999109
641 1157110420118387
642 1193381249032148
643 1230760552916732
644 1269281367033224
645 1308977676427743
646 1349884463168364
647 1392037713955578
648 1435474469490863
649 1480232833011816
650 1526352021911138
651 1573872377297412
652 1622835417917862
653 1673283850834384
654 1725261627795633
655 1778813957052202
656 1833987362311047
657 1890829695805541
658 1949390199901039
659 2009719521524046
660 2071869776581205
661 2135894565782763
662 2201849042029207
663 2269789927761865
664 2339775585399190
665 2411866036335788
666 2486123034614787
667 2562610087624084
668 2641392533178263
669 2722537562064680
670 2806114298637765
671 2892193825356138
672 2980849267098133
673 3072155817754870
674 3166190828467975
675 3263033836454319
676 3362766657287753
677 3465473416119674
678 3571240644244693
679 3680157312801403
680 3792314933849112
681 3907807596751144
682 4026732073912318
683 4149187860035690
684 4275277282790690
685 4405105545050792
686 4538780840755366
687 4676414400361382
688 4818120612075296
689 4964017070740762
690 5114224704750898
691 5268867828506980
692 5428074275309343
693 5591975453655701
694 5760706486324301
695 5934406270770092
696 6113217624750749
697 6297287350987944
698 6486766389681232
699 6681809887744338
700 6882577358457787
701 7089232755580364
702 7301944640543656
703 7520886261644093
704 7746235729171756
705 7978176100040627
706 8216895561152573
707 8462587519814703
708 8715450795795271
709 8975689717778394
710 9243514324565650
711 9519140467981078
712 9802790023570614
713 10094691000362576
714 10395077761590320
715 10704191141611311
716 11022278677170399
717 11349594731954149
718 11686400738813598
719 12032965332424480
720 12389564603066551
721 12756482237754676
722 13134009786172574
723 13522446810825206
724 13922101165615907
725 14333289155566519
726 14756335828724908
727 15191575145890174
728 15639350286533389
729 16100013829163492
730 16573928071839457
731 17061465223811240
732 17563007741405747
733 18078948531464518
734 18609691303392158
735 19155650785125054
736 19717253092015862
737 20294935956069104
738 20889149112561799
739 21500354543166276
740 22129026881209237
741 22775653669529904
742 23440735785169967
743 24124787712820339
744 24828337989968980
745 25551929496671523
746 26296119922198595
747 27061482072109883
748 27848604357322201
749 28658091119476047
750 29490563143606135
751 30346658002669548
752 31227030595011677
753 32132353509187047
754 33063317587300079
755 34020632311264792
756 35005026393370798
757 36017248185006258
758 37058066295825338
759 38128270026240566
760 39228670016444750
761 40360098704000285
762 41523411004269138
763 42719484794303937
764 43949221626263456
765 45213547239113528
766 46513412306491420
767 47849792977753500
768 49223691662065613
769 50636137600211536
770 52088187686728404
771 53580927074216886
772 55115470035217661
773 56692960600801670
774 58314573464231884
775 59981514655490391
776 61695022488811849
777 63456368275156515
778 65266857315590273
779 67127829653760690
780 69040661117464177
781 71006764113062696
782 73027588717642401
783 75104623517689120
784 77239396754124261
785 79433477207617402
786 81688475399191383
787 84006044524434604
788 86387881712433733
789 88835729011559647
790 91351374709383409
791 93936654372784611
792 96593452231934287
793 99323702277363627
794 102129389711190862
795 105012552104234241
796 107975280917552793
797 111019722722778633
798 114148080797516942
799 117362616411969389
800 120665650501839203
801 124059565024801170
802 127546804714470862
803 131129878510387203
804 134811361397108709
805 138593895911281165
806 142480194070057640
807 146473038959349190
808 150575286755677911
809 154789868399841519
810 159119791716869172
811 163568143179250212
812 168138090129808756
813 172832882639217945
814 177655855836548814
815 182610431865951040
816 187700122330228658
817 192928530351503135
818 198299353133356000
819 203816384130912583
820 209483515737036505
821 215304741567462360
822 221284159277191537
823 227425972966256419
824 233734496132674411
825 240214154205105693
826 246869487638703016
827 253705154581150141
828 260725934118456093
829 267936729080839495
830 275342569445775762
831 282948615290935576
832 290760160361787016
833 298782635179061712
834 307021610779006415
835 315482801982857948
836 324172071318128671
837 333095432458384372
838 342259054333988251
839 351669264750788308
840 361332554699597617
841 371255582162440155
842 381445176630400690
843 391908343106969584
844 402652266843959575
845 413684317551856549
846 425012054364452684
847 436643230266194386
848 448585797296579759
849 460847911205473914
850 473437936908444798
851 486364453381445207
852 499636259379290584
853 513262378581240272
854 527252065585302925
855 541614811317327054
856 556360349313984389
857 571498661408480145
858 587039984316214702
859 602994815610416019
860 619373920625023336
861 636188338734731361
862 653449390589885303
863 671168684716009020
864 689358125096750716
865 708029918108228267
866 727196580466714593
867 746870946514443526
868 767066176549027378
869 787795764478043492
870 809073546548575422
871 830913709388242751
872 853330799153991067
873 876339729978674933
874 899955793558631798
875 924194668025713918
876 949072427994708999
877 974605553881153356
878 1000810942430531167
879 1027705916503803356
880 1055308236110812032
881 1083636108686369779
882 1112708200652007099
883 1142543648206013508
884 1173162069438649810
885 1204583575661308406
886 1236828784100946514
887 1269918829794585786
888 1303875378890599071
889 1338720641135444202
890 1374477383810594578
891 1411168944840373743
892 1448819247394073407
893 1487452813644970550
894 1527094780069281508
895 1567770911887267611
896 1609507619091986967
897 1652331971605585483
898 1696271716071743116
899 1741355291761649285
900 1787611848166358834
901 1835071261687947353
902 1883764154069527052
903 1933721909909515578
904 1984976695968162091
905 2037561479544478790
906 2091510048700731749
907 2146857031542780193
908 2203637917405728512
909 2261889077081134545
910 2321647785008357553
911 2382952240493956776
912 2445841590956148429
913 2510355954183140917
914 2576536442680140694
915 2644425187016401268
916 2714065361325781465
917 2785501207794423340
918 2858778063369102321
919 2933942385439139522
920 3011041779809085853
921 3090125027631858655
922 3171242114704174991
923 3254444259710358436
924 3339783944902525735
925 3427314945716504782
926 3517092362901447471
927 3609172653573083537
928 3703613664859608657
929 3800474666460317102
930 3899816385878654222
931 4001701042556617056
932 4106192384768892227
933 4213355725407646690
934 4323257980614251252
935 4435967707292316343
936 4551555143557995637
937 4670092248061869366
938 4791652742342323846
939 4916312152041626422
940 5044147851249861973
941 5175239105704247696
942 5309667119216170482
943 5447515078945998242
944 5588868204009741175
945 5733813792926931797
946 5882441274506941613
947 6034842257571743292
948 6191110584227560381
949 6351342381968061104
950 6515636119441601827
951 6684092661046366029
952 6856815325307508758
953 7033909942080606237
954 7215484913659374292
955 7401651274708135266
956 7592522756225992064
957 7788215848335714138
958 7988849867234972778
959 8194547020974596432
960 8405432479534589125
961 8621634443729737100
962 8843284218554115810
963 9070516285359551640
964 9303468378617756783
965 9542281561523490275
966 9787100306331488944
967 10038072573541992740
968 10295349895976438537
969 10559087461711470268
970 10829444202063673983
971 11106582878445435100
972 11390670174437984977
973 11681876786749187965
974 11980377521561963724
975 12286351389783598700
976 12599981707863852029
977 12921456197533650785
978 13250967091297336602
979 13588711236866352088
980 13934890207538940287
981 14289710411545134076
982 14653383207535597447
983 15026125019063657737
984 15408157455416363342
985 15799707431468217408
986 16201007294097659576
987 16612294947659212345
988 17033813986238187978
989 17465813824998707536
990 17908549838542292090
991 18362283498399467492
992 18827282517769406674
993 19303820995436408076
994 19792179567178811945
995 20292645556403890437
996 20805513132528704905
997 21331083468638715878
998 21869664907156394466
999 22421573124844157274
1000 22987131306089186602