0 1
1 2
2 1
3 1
4 3
5 4
6 3
7 4
8 7
9 7
10 8
11 11
12 13
13 15
14 18
15 21
16 25
17 31
18 34
19 38
20 48
21 56
22 61
23 72
24 85
25 95
26 109
27 126
28 142
29 163
30 186
31 207
32 237
33 272
34 301
35 339
36 389
37 433
38 482
39 547
40 612
41 680
42 764
43 851
44 946
45 1061
46 1177
47 1301
48 1455
49 1616
50 1779
51 1977
52 2194
53 2415
54 2670
55 2953
56 3250
57 3586
58 3953
59 4338
60 4778
61 5261
62 5760
63 6323
64 6952
65 7607
66 8327
67 9131
68 9982
69 10911
70 11937
71 13025
72 14216
73 15531
74 16919
75 18429
76 20104
77 21879
78 23789
79 25901
80 28160
81 30582
82 33238
83 36084
84 39143
85 42490
86 46065
87 49898
88 54096
89 58589
90 63382
91 68614
92 74239
93 80232
94 86737
95 93735
96 101205
97 109292
98 117973
99 127234
100 137257
101 148020
102 159474
103 171841
104 185143
105 199297
106 214523
107 230893
108 248333
109 267060
110 287161
111 308570
112 331545
113 356194
114 382417
115 410513
116 440664
117 472739
118 507026
119 543793
120 582935
121 624724
122 669466
123 717091
124 767914
125 822286
126 880118
127 941768
128 1007704
129 1077826
130 1152473
131 1232238
132 1317089
133 1407345
134 1503664
135 1606100
136 1715022
137 1831167
138 1954612
139 2085782
140 2225582
141 2374127
142 2531825
143 2699759
144 2878191
145 3067517
146 3268922
147 3482840
148 3709755
149 3950971
150 4207027
151 4478504
152 4766939
153 5073004
154 5397300
155 5741615
156 6106887
157 6493754
158 6904170
159 7339387
160 7800211
161 8288781
162 8806591
163 9354648
164 9935426
165 10550706
166 11201608
167 11890971
168 12621048
169 13393115
170 14210278
171 15075326
172 15989877
173 16957347
174 17980988
175 19062824
176 20206771
177 21416619
178 22694721
179 24045551
180 25473684
181 26981876
182 28575065
183 30258712
184 32036241
185 33913129
186 35895657
187 37988032
188 40196532
189 42528385
190 44988532
191 47584152
192 50323744
193 53213130
194 56260321
195 59475250
196 62864985
197 66438505
198 70207145
199 74179424
200 78365668
201 82778801
202 87428800
203 92327528
204 97489956
205 102927769
206 108654344
207 114686963
208 121039552
209 127727255
210 134769695
211 142183373
212 149985754
213 158199120
214 166842663
215 175936505
216 185506226
217 195574134
218 206163112
219 217302462
220 229018383
221 241336959
222 254291380
223 267912287
224 282229793
225 297281506
226 313102806
227 329728422
228 347201312
229 365562301
230 384851065
231 405116598
232 426406306
233 448765574
234 472249857
235 496914040
236 522810461
237 550001902
238 578551362
239 608519137
240 639976728
241 672996371
242 707647049
243 744010130
244 782168783
245 822201967
246 864201758
247 908263712
248 954478674
249 1002950878
250 1053789444
251 1107098756
252 1162997329
253 1221609668
254 1283055107
255 1347468317
256 1414991733
257 1485761770
258 1559930852
259 1637661679
260 1719110681
261 1804450416
262 1893865919
263 1987536361
264 2085657702
265 2188440242
266 2296088392
267 2408824580
268 2526888252
269 2650512526
270 2779949156
271 2915470444
272 3057342744
273 3205851024
274 3361303990
275 3524005640
276 3694279205
277 3872474475
278 4058937371
279 4254034381
280 4458162328
281 4671714612
282 4895105863
283 5128785864
284 5373202505
285 5628824849
286 5896161521
287 6175721943
288 6468037494
289 6773683092
290 7093236798
291 7427300307
292 7776524005
293 8141563453
294 8523098820
295 8921865356
296 9338606920
297 9774092248
298 10229151098
299 10704626795
300 11201388901
301 11720373462
302 12262534838
303 12828856175
304 13420393986
305 14038227653
306 14683467225
307 15357304506
308 16060960579
309 16795688430
310 17562830718
311 18363767766
312 19199914536
313 20072783113
314 20983931591
315 21934957082
316 22927562984
317 23963507085
318 25044590061
319 26172729915
320 27349909833
321 28578159259
322 29859635625
323 31196574916
324 32591264851
325 34046131364
326 35563692547
327 37146526002
328 38797359974
329 40519028825
330 42314433991
331 44186642361
332 46138844065
333 48174303783
334 50296466227
335 52508919836
336 54815337995
337 57219588519
338 59725704111
339 62337816027
340 65060267241
341 67897587582
342 70854419436
343 73935637340
344 77146328802
345 80491708438
346 83977243587
347 87608645122
348 91391769700
349 95332747551
350 99437984332
351 103714054672
352 108167831551
353 112806496822
354 117637425845
355 122668321385
356 127907233969
357 133362433778
358 139042548356
359 144956597783
360 151113853769
361 157523976440
362 164197065601
363 171143511056
364 178374127558
365 185900219348
366 193733421798
367 201885837786
368 210370116782
369 219199283769
370 228386875957
371 237947042114
372 247894359175
373 258243963612
374 269011672343
375 280213792108
376 291867244260
377 303989703903
378 316599402638
379 329715250309
380 343356993689
381 357545008389
382 372300416248
383 387645269916
384 403602334873
385 420195195818
386 437448468404
387 455387577870
388 474038852860
389 493429760198
390 513588681349
391 534544997681
392 556329349590
393 578973406464
394 602509941878
395 626973124018
396 652398280851
397 678821957635
398 706282239754
399 734818521171
400 764471542489
401 795283741049
402 827299024744
403 860562795406
404 895122327185
405 931026541391
406 968326013570
407 1007073387834
408 1047323155305
409 1089131636309
410 1132557431458
411 1177661213563
412 1224505683343
413 1273156050783
414 1323679843569
415 1376146842072
416 1430629591632
417 1487203223301
418 1545945366593
419 1606936700933
420 1670260792270
421 1736003974271
422 1804255939333
423 1875109603062
424 1948660952567
425 2025009669021
426 2104259024133
427 2186515702893
428 2271890457804
429 2360498033094
430 2452456960948
431 2547890256193
432 2646925373082
433 2749693965085
434 2856332619882
435 2966982863055
436 3081790880786
437 3200908285466
438 3324492171573
439 3452704810736
440 3585714447432
441 3723695402773
442 3866827742009
443 4015298109779
444 4169299887878
445 4329032825032
446 4494703910949
447 4666527605057
448 4844725429209
449 5029526868818
450 5221169679125
451 5419899453032
452 5625970548364
453 5839646467244
454 6061199400642
455 6290911192147
456 6529073797746
457 6775988797373
458 7031968393838
459 7297335972862
460 7572425584138
461 7857582961675
462 8153166192139
463 8459545181248
464 8777102694165
465 9106235127385
466 9447351964447
467 9800876848100
468 10167248464392
469 10546919978814
470 10940360138607
471 11348054291996
472 11770503810108
473 12208227203809
474 12661761287433
475 13131660607113
476 13618498570691
477 14122868750911
478 14645384327351
479 15186679243056
480 15747409657309
481 16328253393808
482 16929911122811
483 17553107989752
484 18198593078814
485 18867140603389
486 19559551721359
487 20276654040898
488 21019302818404
489 21788382954917
490 22584808555627
491 23409524151880
492 24263506890517
493 25147766142328
494 26063344748001
495 27011321430410
496 27992810466110
497 29008962937427
498 30060969380226
499 31150059552769
500 32277503694861
501 33444615404999
502 34652751523974
503 35903313422030
504 37197750119061
505 38537558281840
506 39924283541516
507 41359523891515
508 42844929818882
509 44382205634750
510 45973113164531
511 47619472057152
512 49323161132904
513 51086122359525
514 52910361363995
515 54797948825224
516 56751024752174
517 58771799202298
518 60862553725873
519 63025645986162
520 65263510713280
521 67578661185017
522 69973694206757
523 72451291356109
524 75014220510336
525 77665341179995
526 80407606078200
527 83244062731732
528 86177859188019
529 89212245920066
530 92350577535179
531 95596318902241
532 98953047431778
533 102424454872051
534 106014353878716
535 109726680739563
536 113565497277117
537 117534997856337
538 121639512599764
539 125883509446913
540 130271601624939
541 134808551374386
542 139499272190527
543 144348836813381
544 149362481516710
545 154545608529782
546 159903794575398
547 165442795809639
548 171168550456530
549 177087187893465
550 183205034302470
551 189528615586431
552 196064667035336
553 202820139721385
554 209802203738107
555 217018258516745
556 224475940034901
557 232183124391003
558 240147938809661
559 248378769773400
560 256884266984298
561 265673355065034
562 274755242693909
563 284139427047568
564 293835706243785
565 303854189528460
566 314205302263690
567 324899799200232
568 335948775808056
569 347363673842882
570 359156295502819
571 371338816039776
572 383923789983806
573 396924166203405
574 410353301903041
575 424224969633331
576 438553373320265
577 453353163719852
578 468639446310449
579 484427798405026
580 500734286182969
581 517575473527645
582 534968440300030
583 552930801120630
584 571480715269223
585 590636906160369
586 610418682013544
587 630845946989229
588 651939221960515
589 673719667172276
590 696209094754064
591 719429990939030
592 743405540870372
593 768159642596228
594 793716930849309
595 820102804219790
596 847343440800530
597 875465823601333
598 904497770269928
599 934467950623059
600 965405913832024
601 997342120833813
602 1030307963948695
603 1064335796040934
604 1099458965828986
605 1135711839753267
606 1173129833276886
607 1211749449374969
608 1251608302890660
609 1292745154099784
610 1335199950619849
611 1379013854571200
612 1424229278604301
613 1470889931427526
614 1519040848054876
615 1568728428574103
616 1620000487570609
617 1672906287706139
618 1727496581466525
619 1783823664842723
620 1841941414572271
621 1901905333064361
622 1963772606658992
623 2027602146956139
624 2093454639205257
625 2161392605420793
626 2231480450189151
627 2303784512905035
628 2378373136114220
629 2455316716152072
630 2534687759570657
631 2616560957178737
632 2701013239969743
633 2788123840044293
634 2877974370777851
635 2970648888606397
636 3066233958856285
637 3164818742428811
638 3266495063979202
639 3371357483180291
640 3479503388423392
641 3591033071892613
642 3706049806754559
643 3824659948492939
644 3946973017504701
645 4073101782672391
646 4203162370913654
647 4337274358057845
648 4475560859387532
649 4618148647946482
650 4765168254427233
651 4916754065407030
652 5073044451090824
653 5234181874912300
654 5400313000162156
655 5571588827984674
656 5748164817544236
657 5930201001716424
658 6117862136127135
659 6311317830895568
660 6510742676216615
661 6716316403201032
662 6928224028186964
663 7146655989211103
664 7371808319570271
665 7603882805674525
666 7843087135388749
667 8089635085409455
668 8343746693813542
669 8605648421237573
670 8875573353144825
671 9153761388416685
672 9440459414531094
673 9735921525777452
674 10040409229232456
675 10354191635306049
676 10677545693160610
677 11010756415409567
678 11354117085401587
679 11707929511313218
680 12072504271129425
681 12448160938041839
682 12835228354684480
683 13234044900191071
684 13644958735323003
685 14068328098320350
686 14504521595846777
687 14953918469719282
688 15416908916092801
689 15893894402123332
690 16385287956200072
691 16891514512445776
692 17413011255201154
693 17950227934694054
694 18503627238866634
695 19073685168074067
696 19660891378423797
697 20265749582974406
698 20888777959089118
699 21530509521996998
700 22191492557715637
701 22872291065553848
702 23573485164514258
703 24295671560621950
704 25039464027409105
705 25805493847853841
706 26594410318867217
707 27406881272953902
708 28243593558755455
709 29105253585527353
710 29992587889261990
711 30906343655303705
712 31847289306035400
713 32816215114853352
714 33813933774443703
715 34841281031313265
716 35899116351429554
717 36988323537883358
718 38109811416028585
719 39264514555053656
720 40453393939224204
721 41677437707541026
722 42937661935666401
723 44235111365443938
724 45570860203475510
725 46946012967998987
726 48361705281580829
727 49819104733540595
728 51319411796911506
729 52863860689418572
730 54453720304893357
731 56090295206020530
732 57774926559309980
733 59508993140879513
734 61293912410939051
735 63131141529101626
736 65022178440539849
737 66968563038431175
738 68971878266256583
739 71033751291010743
740 73155854760511014
741 75339907999663731
742 77587678277739648
743 79900982168177017
744 82281686846553833
745 84731711459301113
746 87253028594005057
747 89847665687634977
748 92517706504873516
749 95265292727330871
750 98092625481026174
751 101001966933378603
752 103995642010616906
753 107076040053998881
754 110245616545000380
755 113506894961134281
756 116862468571363113
757 120315002299558851
758 123867234729493790
759 127521980050940246
760 131282130072512871
761 135150656387189557
762 139130612481237760
763 143225135908666228
764 147437450629753887
765 151770869295640214
766 156228795597326712
767 160814726790891052
768 165532256171826616
769 170385075612306632
770 175376978287546207
771 180511861355311863
772 185793728696506751
773 191226693857994802
774 196814982953613290
775 202562937624580004
776 208475018215541447
777 214555806914407249
778 220810010950091625
779 227242466020099084
780 233858139688108776
781 240662134837656274
782 247659693370679028
783 254856199883502715
784 262257185396816125
785 269868331345796633
786 277695473556422664
787 285744606273967099
788 294021886467202567
789 302533638128336366
790 311286356623660592
791 320286713336351356
792 329541560315407350
793 339057934973621180
794 348843065095031080
795 358904373860476691
796 369249484920328211
797 379886227794317305
798 390822643303078631
799 402066989045509588
800 413627745221153472
801 425513620498985997
802 437733557931231999
803 450296741231096605
804 463212601112763943
805 476490821675601417
806 490141347172165608
807 504174388856281015
808 518600431874524257
809 533430242561729711
810 548674875836416152
811 564345682639618697
812 580454317798312957
813 597012748010042482
814 614033259871840113
815 631528468355411889
816 649511325426343372
817 667995128708730756
818 686993530618881638
819 706520547668254175
820 726590569813283891
821 747218370297499446
822 768419115690612174
823 790208375977168379
824 812602135161154114
825 835616802097162196
826 859269221375133161
827 883576684745998783
828 908556942805450986
829 934228216735942949
830 960609210615882874
831 987719124021453970
832 1015577664692099178
833 1044205061790041749
834 1073622079490016547
835 1103850030639874270
836 1134910791042671450
837 1166826814108914528
838 1199621145588827020
839 1233317438955109237
840 1267939971198300194
841 1303513658712524875
842 1340064073862379233
843 1377617462008446864
844 1416200758634949315
845 1455841607189969124
846 1496568377434091591
847 1538410183905458508
848 1581396905129701809
849 1625559203391054777
850 1670928544636902193
851 1717537219161469259
852 1765418362906597200
853 1814605978914963765
854 1865134959598773032
855 1917041109685797109
856 1970361169339082396
857 2025132838129622236
858 2081394799751215980
859 2139186746933731622
860 2198549407248124213
861 2259524569722197910
862 2322155111683317150
863 2386485026534184799
864 2452559452411862884
865 2520424701105291123
866 2590128287949879237
867 2661718962683140643
868 2735246740593682216
869 2810762934693015952
870 2888320188931770919
871 2967972511748923569
872 3049775310691528228
873 3133785428166858750
874 3220061177572407245
875 3308662380547398536
876 3399650405449653415
877 3493088206259495206
878 3589040362659771801
879 3687573121440623652
880 3788754438385225685
881 3892654021388837125
882 3999343375008778839
883 4108895845555771649
884 4221386667478639859
885 4336893011291945237
886 4455494032112303806
887 4577270919552614073
888 4702306949277384907
889 4830687535240158417
890 4962500283348225141
891 5097835046914513020
892 5236783982871588305
893 5379441609486148165
894 5525904865995075964
895 5676273173092194351
896 5830648494992915864
897 5989135403562154746
898 6151841143390699197
899 6318875698532976032
900 6490351861457523367
901 6666385303052021260
902 6847094644379778528
903 7032601530808103649
904 7223030707306324316
905 7418510095590879562
906 7619170873811724899
907 7825147557534733261
908 8036578082672875598
909 8253603891137364794
910 8476370017923170504
911 8705025180253306131
912 8939721869631519458
913 9180616445478935563
914 9427869230948406666
915 9681644611847766501
916 9942111137308665591
917 10209441622760009086
918 10483813256223532352
919 10765407706531248528
920 11054411233983090142
921 11351014804551625512
922 11655414206200579419
923 11967810167790405864
924 12288408481768316305
925 12617420129178914506
926 12955061407420898083
927 13301554062040663766
928 13657125421069261296
929 14022008532275678485
930 14396442304725417062
931 14780671653124131511
932 15174947645260111713
933 15579527654035391369
934 15994675512543844397
935 16420661672445913315
936 16857763367231215643
937 17306264778809600202
938 17766457207613086598
939 18238639247903906910
940 18723116966713353285
941 19220204086521451959
942 19730222173481075842
943 20253500829599640451
944 20790377888908599869
945 21341199619534930036
946 21906320930082965229
947 22486105580271623460
948 23080926397851653225
949 23691165500211472927
950 24317214520528177844
951 24959474840600673003
952 25618357828776834269
953 26294285082737243067
954 26987688679388715512
955 27699011430288616722
956 28428707142260559486
957 29177240885572401582
958 29945089268115094252
959 30732740715135396127
960 31540695757009901049
961 32369467323522998366
962 33219581044090927424
963 34091575556536908784
964 34986002822908501402
965 35903428451662774261
966 36844432028945029152
967 37809607457488108061
968 38799563302333065990
969 39814923146218124162
970 40856325953209150801
971 41924426439641990818
972 43019895455342270512
973 44143420373750293559
974 45295705489887919940
975 46477472429251627613
976 47689460566319648748
977 48932427451471058881
978 50207149249521847890
979 51514421188635206956
980 52855058018256635294
981 54229894479398871821
982 55639785786115548450
983 57085608116661549089
984 58568259117780994474
985 60088658421053320437
986 61647748169640509006
987 63246493558990768662
988 64885883390528111299
989 66566930636510883944
990 68290673019729978366
991 70058173607186004310
992 71870521415760560791
993 73728832033665360236
994 75634248256932729023
995 77587940738790072742
996 79591108655809151696
997 81644980390229644636
998 83750814226125858012
999 85909899063411318956
1000 88123555149225620521