0 1
1 1
2 2
3 1
4 3
5 3
6 5
7 5
8 8
9 8
10 12
11 12
12 19
13 19
14 27
15 28
16 39
17 41
18 55
19 58
20 77
21 82
22 106
23 113
24 145
25 156
26 196
27 210
28 262
29 283
30 348
31 376
32 459
33 497
34 600
35 651
36 781
37 849
38 1009
39 1097
40 1298
41 1413
42 1660
43 1807
44 2113
45 2302
46 2676
47 2916
48 3377
49 3681
50 4242
51 4623
52 5309
53 5787
54 6619
55 7214
56 8225
57 8964
58 10184
59 11096
60 12573
61 13697
62 15472
63 16849
64 18986
65 20672
66 23232
67 25285
68 28353
69 30849
70 34512
71 37535
72 41909
73 45563
74 50766
75 55168
76 61357
77 66653
78 73992
79 80342
80 89042
81 96643
82 106929
83 116003
84 128158
85 138975
86 153302
87 166163
88 183041
89 198311
90 218153
91 236241
92 259549
93 280943
94 308270
95 333527
96 365542
97 395314
98 432754
99 467783
100 511534
101 552694
102 603737
103 652018
104 711517
105 768077
106 837332
107 903487
108 984030
109 1061310
110 1154852
111 1244995
112 1353542
113 1458564
114 1584363
115 1706553
116 1852220
117 1994220
118 2162693
119 2327505
120 2522194
121 2713269
122 2937998
123 3159253
124 3418444
125 3674380
126 3973002
127 4268715
128 4612484
129 4953808
130 5349158
131 5742706
132 6197013
133 6650332
134 7171889
135 7693524
136 8291820
137 8891506
138 9577213
139 10265955
140 11051243
141 11841556
142 12740110
143 13646133
144 14673527
145 15711305
146 16885037
147 18072672
148 19412617
149 20770624
150 22299109
151 23850608
152 25592927
153 27364066
154 29348624
155 31368859
156 33627781
157 35930363
158 38499692
159 41122033
160 44042472
161 47026757
162 50343943
163 53737576
164 57502949
165 61359311
166 65630517
167 70009538
168 74851459
169 79820523
170 85305804
171 90940488
172 97150781
173 103535967
174 110562626
175 117793418
176 125738978
177 133922043
178 142901141
179 152155892
180 162297040
181 172757251
182 184203995
183 196019271
184 208932344
185 222270113
186 236828923
187 251876238
188 268281423
189 285247387
190 303722733
191 322840766
192 343636267
193 365167019
194 388561271
195 412795441
196 439099353
197 466361242
198 495921028
199 526571987
200 559773614
201 594216369
202 631489301
203 670172219
204 711994769
205 755417082
206 802321042
207 851038074
208 903615181
209 958244707
210 1017152369
211 1078381003
212 1144350037
213 1212940926
214 1286782657
215 1363583325
216 1446198899
217 1532150508
218 1624539573
219 1720686503
220 1823958453
221 1931459545
222 2046844139
223 2166984303
224 2295845158
225 2430048969
226 2573896581
227 2723742410
228 2884250360
229 3051486747
230 3230507544
231 3417070356
232 3616654935
233 3824687123
234 4047104115
235 4278976479
236 4526735592
237 4785070563
238 5060946007
239 5348642799
240 5655701345
241 5975964538
242 6317593845
243 6673963756
244 7053906063
245 7450293162
246 7872679554
247 8313401012
248 8782791742
249 9272612775
250 9794038689
251 10338216631
252 10917227427
253 11521561270
254 12164275385
255 12835158794
256 13548321222
257 14292801937
258 15083844244
259 15909687711
260 16786797124
261 17702557645
262 18674749210
263 19689846303
264 20767045428
265 21891848894
266 23084977899
267 24330899300
268 25651975996
269 27031570379
270 28493811801
271 30020887118
272 31638827031
273 33328565581
274 35118178704
275 36987268003
276 38966110057
277 41032887619
278 43220243754
279 45504853347
280 47921904994
281 50446469261
282 53116471316
283 55905278057
284 58853757355
285 61933465085
286 65188431791
287 68588291711
288 72180475258
289 75932575703
290 79895676558
291 84035207232
292 88406177208
293 92971719747
294 97791061595
295 102824903676
296 108137003737
297 113685484074
298 119538968472
299 125652850015
300 132100979152
301 138835858317
302 145936949753
303 153353699268
304 161171595279
305 169336849356
306 177941418605
307 186928097854
308 196395788875
309 206283674917
310 216698110782
311 227574468093
312 239027101173
313 250987356905
314 263578172896
315 276726652816
316 290564944841
317 305015677140
318 320220878542
319 336098463886
320 352801062495
321 370241623617
322 388584146070
323 407736355668
324 427874446445
325 448900647967
326 471004231639
327 494081652504
328 518336206334
329 543658279904
330 570266205079
331 598044001377
332 627226122505
333 657689906123
334 689687087774
335 723088003895
336 758162916276
337 794774825036
338 833213847861
339 873335309526
340 915450609680
341 959407043178
342 1005538815260
343 1053684833527
344 1104203742546
345 1156925690447
346 1212235506681
347 1269954206436
348 1330494675242
349 1393668408007
350 1459918345684
351 1529046076514
352 1601526739608
353 1677151617882
354 1756430338019
355 1839143482695
356 1925837619244
357 2016282225289
358 2111063429884
359 2209939208086
360 2313538058487
361 2421606049245
362 2534817048587
363 2652904825503
364 2776591831080
365 2905599140234
366 3040701219985
367 3181606074089
368 3329143861915
369 3483009141815
370 3644091693510
371 3812072280694
372 3987904508930
373 4171255007845
374 4363145702086
375 4563228781898
376 4772599300865
377 4990894723027
378 5219288369753
379 5457402737106
380 5706494914378
381 5966172217423
382 6237781379629
383 6520914382920
384 6817013892996
385 7125656447177
386 7448387361488
387 7784767692894
388 8136452595880
389 8502987670895
390 8886145589989
391 9285456615572
392 9702819152607
393 10137748323950
394 10592277043741
395 11065905612199
396 11560810840293
397 12076478627022
398 12615239708601
399 13176566151357
400 13762953342484
401 14373860218203
402 15011958273937
403 15676694199723
404 16370927851618
405 17094094727246
406 17849256130837
407 18635837643379
408 19457116011360
409 20312508387334
410 21205521907544
411 22135567054894
412 23106397336322
413 24117418587236
414 25172647754066
415 26271488374952
416 27418239082696
417 28612303792389
418 29858282311503
419 31155582002284
420 32509124677785
421 33918324613381
422 35388447874774
423 36918919593005
424 38515373863642
425 40177251096591
426 41910578809539
427 43714817685538
428 45596415800411
429 47554859685745
430 49597046953324
431 51722496240896
432 53938585660523
433 56244872912981
434 58649249674961
435 61151320480196
436 63759525897343
437 66473525900963
438 69302347672785
439 72245716202086
440 75313285582599
441 78504856393104
442 81830752666485
443 85290862290877
444 88896225201074
445 92646829506038
446 96554480114021
447 100619279620652
448 104853850322244
449 109258424981304
450 113846499238480
451 118618453301619
452 123588715918224
453 128757833694863
454 134141232282617
455 139739645522592
456 145569564098872
457 151631931900939
458 157944377369934
459 164508079470825
460 171341882057481
461 178447226528349
462 185844255036895
463 193534701370607
464 201540094481839
465 209862493244118
466 218524907863279
467 227529758039167
468 236901636071593
469 246643361444708
470 256781216171189
471 267318462037924
472 278283185654293
473 289679137398352
474 301536331073323
475 313859056095971
476 326679384324120
477 340002199070717
478 353861769884842
479 368263633684631
480 383244406744809
481 398810344447610
482 415000568810531
483 431822124191182
484 449316808052775
485 467492530244896
486 486393944732213
487 506029909949268
488 526448129566472
489 547658500689559
490 569711982807911
491 592619609426935
492 616435815776338
493 641172877622471
494 666888940531926
495 693597637264539
496 721361074012422
497 750194364707095
498 780163843134317
499 811286238861457
500 843632398065899
501 877220811373040
502 912127141103463
503 948371796276640
504 986035579362285
505 1025140987807576
506 1065774309770748
507 1107960314945927
508 1151791145723923
509 1197294042562238
510 1244567395087162
511 1293641128971416
512 1344620300202680
513 1397537751115418
514 1452505650960845
515 1509560008584928
516 1568820583062035
517 1630326819230402
518 1694206574084082
519 1760503019168769
520 1829352651158834
521 1900802681677142
522 1974998824637157
523 2051992669588002
524 2131939763444960
525 2214896437653117
526 2301028728519058
527 2390398101549528
528 2483181782178551
529 2579446792229718
530 2679382292097534
531 2783061314628686
532 2890685750182516
533 3002335131967300
534 3118224927602593
535 3238441697315081
536 3363215389046853
537 3492640156528063
538 3626961390390868
539 3766281447236382
540 3910862185987413
541 4060814821250584
542 4216418773084593
543 4377794818476661
544 4545241103150218
545 4718888723399258
546 4899055791369995
547 5085884536088789
548 5279714358128560
549 5480699492970234
550 5689202038012628
551 5905389173696392
552 6129647194707566
553 6362157234085106
554 6603331382158258
555 6853365806434197
556 7112700095537086
557 7381546612521874
558 7660374257857753
559 7949412836227397
560 8249162491623875
561 8559871807131294
562 8882074227546240
563 9216038548397132
564 9562333706328612
565 9921250247130419
566 10293394932559059
567 10679081707721793
568 11078957644188079
569 11493361854103472
570 11922984364549926
571 12368191349568912
572 12829718608858875
573 13307961408823347
574 13803704321096175
575 14317373880128859
576 14849806622768265
577 15401462682076136
578 15973233959569169
579 16565616683260030
580 17179561738222802
581 17815604120539204
582 18474757550966497
583 19157598655912675
584 19865208092133859
585 20598207180281785
586 21357747877214065
587 22144499477414365
588 22959689882595978
589 23804039870577660
590 24678858230948488
591 25584920980156706
592 26523623055971895
593 27495799730750643
594 28502937687917527
595 29545935752984591
596 30626378311120410
597 31745232336607036
598 32904186253503817
599 34104280099208120
600 35347313079047946
601 36634403547504799
602 37967468664107830
603 39347710717067591
604 40777172450845834
605 42257146090412922
606 43789808082257010
607 45376547003611162
608 47019681637146863
609 48720703767229116
610 50482083696142425
611 52305423739127943
612 54193355485370329
613 56147599604095857
614 58170959358846669
615 60265282128678758
616 62433553898072424
617 64677757679039311
618 67001073923627118
619 69405630804935859
620 71894815733123137
621 74470912214641565
622 77137527898325227
623 79897112483007864
624 82753507976173433
625 85709341859117361
626 88768705509294959
627 91934416559759959
628 95210831716192076
629 98600971962023563
630 102109476294833539
631 105739583130770512
632 109496231790959436
633 113382893146989086
634 117404826008997239
635 121565749728530899
636 125871262974398125
637 130325350668474462
638 134933972986201862
639 139701398645312898
640 144633972333304761
641 149736265996832166
642 155015033281720507
643 160475170082341816
644 166123864978984732
645 171966359900010934
646 178010305959979926
647 184261314663181359
648 190727528981997882
649 197414955086539938
650 204332258959812609
651 211485868175027718
652 218885004820341073
653 226536546360879697
654 234450306144825268
655 242633641881640381
656 251096995521158859
657 259848237350686078
658 268898477583416499
659 278256133525370526
660 287933025776907125
661 297938155343468883
662 308284097948309720
663 318980477359077846
664 330040671929093959
665 341474969782383605
666 353297602349274887
667 365519566395899699
668 378155999995436627
669 391218655701646092
670 404723635104362770
671 418683496730588590
672 433115366069696589
673 448032661037120337
674 463453595126025492
675 479392502487940318
676 495868752671190168
677 512897656556873952
678 530499811985279483
679 548691570934619054
680 567494836212707948
681 586927069376595743
682 607011559583427128
683 627766950821694413
684 649218004970123904
685 671384625942289883
686 694293140001323153
687 717964793409158720
688 742427574085519866
689 767704158297460831
690 793824298839513655
691 820812195198466997
692 848699474565406526
693 877511958760944659
694 907283265575558744
695 938040944541717331
696 969820727334030169
697 1002652003222756222
698 1036572748556615350
699 1071614311426891568
700 1107817051600891929
701 1145214402562864402
702 1183849254672210284
703 1223757261326513168
704 1264983999583265303
705 1307567485706747666
706 1351556149022821864
707 1396990520564907966
708 1443922057525857211
709 1492393967103834305
710 1542460920581464100
711 1594168972789621964
712 1647576206579463963
713 1702731706565629618
714 1759697176569934285
715 1818524924474752178
716 1879280497105593743
717 1942019631114777659
718 2006811951742846860
719 2073716842661377525
720 2142808257107738795
721 2214149457537970260
722 2287818989775299077
723 2363884241158610811
724 2442428630579951693
725 2523523931554769867
726 2607258733357455223
727 2693709473085235646
728 2782970225531219933
729 2875122385857712663
730 2970265848383925043
731 3068487278925338253
732 3169892745315855305
733 3274574515800362232
734 3382645206869938014
735 3494203041313536189
736 3609367581817631341
737 3728243379382152435
738 3850957364134629956
739 3977620811793528879
740 4108368466269318035
741 4243318748706837901
742 4382614689704461371
743 4526382302184213932
744 4674773404453175760
745 4827922074726856066
746 4985989449797678731
747 5149118175471440679
748 5317479269294078386
749 5491224477443428753
750 5670535293811780355
751 5855573130023147318
752 6046530587173446438
753 6243579341606968279
754 6446923769793533012
755 6656746448294009193
756 6873264236602729343
757 7096671285349968927
758 7327197686474302148
759 7565049879146748497
760 7810471981360039326
761 8063683478303152224
762 8324943354379670677
763 8594484943809099235
764 8872582987213253686
765 9159485519059785940
766 9455483978301906276
767 9760842001905952080
768 10075868724594588193
769 10400844342100903183
770 10736096740867717444
771 11081923688841110522
772 11438672942017730546
773 11806660914516843698
774 12186256415163915534
775 12577795642257230894
776 12981669709928963190
777 13398235806435182536
778 13827908676866720139
779 14271067776934398971
780 14728152885711048948
781 15199567079741096658
782 15685776656904989022
783 16187209748247675093
784 16704360741767659224
785 17237684341615354228
786 17787704688645328049
787 18354904668576138598
788 18939839934506712433
789 19543023257235877000
790 20165043663658030786
791 20806445613705575449
792 21467853477606264329
793 22149845314815660314
794 22853082922566192706
795 23578179982691222612
796 24325837923725616601
797 25096708191667226374
798 25891534178129824264
799 26711007360832522294
800 27555915560960546327
801 28426992688496147709
802 29325073603041853891
803 30250937187997549894
804 31205468100647567391
805 32189492887624135799
806 33203948922086826866
807 34249713260881245531
808 35327779079150736173
809 36439076957075684485
810 37584659135287948764
811 38765512906048120156
812 39982753026387512259
813 41237426875021123736
814 42530715374257327481
815 43863729559839532774
816 45237720377345559707
817 46653866297472199865
818 48113492367934107743
819 49617848491437724990
820 51168338129989992936
821 52766286846920557351
822 54413181077065673504
823 56110426517673947005
824 57859597395148223672
825 59662184272477333825
826 61519854261143166539
827 63434187794841138292
828 65406950253800066912
829 67439817235952101265
830 69534658080316896045
831 71693249147438016663
832 73917569748660667424
833 76209502927528426184
834 78571144322785891371
835 81004489921505703611
836 83511758405485855278
837 86095065325112017767
838 88756759501547623896
839 91499083047707294140
840 94324522422269723732
841 97235453700601417303
842 100234508901215048597
843 103324205885013414458
844 106507330600384654780
845 109786550963688285932
846 113164815695784322209
847 116644951510228816550
848 120230079241693859702
849 123923193640830013860
850 127727597523813145657
851 131646463444235414099
852 135683286622932435013
853 139841427737530462933
854 144124585422832425399
855 148536319387743877236
856 153080543308850865123
857 157761027452314888119
858 162581912816932772854
859 167547192405195642662
860 172661247507105445557
861 177928306729874685069
862 183353005350164120989
863 188939821175820064491
864 194693657932020326475
865 200619256990939939996
866 206721805796630922799
867 213006324459533334604
868 219478300265799162063
869 226143048093054922191
870 233006372092399665639
871 240073898839732292114
872 247351767322841931417
873 254845933698864255864
874 262562890764833823640
875 270508943146379480599
876 278690957477859898661
877 287115606800170094680
878 295790152726234037549
879 304721657776718709012
880 313917800858252469366
881 323386056214845966696
882 333134543599849231175
883 343171172467901955089
884 353504528277381465475
885 364142980492658647422
886 375095606511737370419
887 386371261991413627889
888 397979543955014751010
889 409929821893652179763
890 422232241671557757193
891 434896715794916734775
892 447933969797323701545
893 461354490003579328969
894 475169614145379978313
895 489390434880885504294
896 504028936460974851592
897 519096852196233219401
898 534606849067089523539
899 550571337258049549156
900 567003704680846480102
901 583917076621145024517
902 601325602222630986301
903 619243162213943414691
904 637684709483476264136
905 656664922773835980216
906 676199603562185183495
907 696304273525978469236
908 716995630032024524512
909 738290085090489195367
910 760205281847656488663
911 782758572655104377765
912 805968599056494027865
913 829853706505277028717
914 854433590434915077815
915 879727645061358500711
916 905756678228990914941
917 932541191633274802728
918 960103167241618499939
919 988464276166897724026
920 1017647739573459726004
921 1047676463323536246618
922 1078574976393935741854
923 1110367488304536467540
924 1143079908190985967379
925 1176737821907327777544
926 1211368595024445405917
927 1246999266377295729212
928 1283658738388026361914
929 1321375583702076034440
930 1360180326369091703941
931 1400103158081163584329
932 1441176313884006502126
933 1483431694394624745133
934 1526903339859948744158
935 1571624954590113553075
936 1617632483332003830544
937 1664961534007865743925
938 1713650060527274813488
939 1763735679768813024585
940 1815258465115995147115
941 1868258153462002350076
942 1922777053923365315126
943 1978857140484068131273
944 2036543080515464552155
945 2095879208506207180277
946 2156912679198267792539
947 2219690317672908079956
948 2284261902100974786520
949 2350676885272248562868
950 2418987812153711259046
951 2489246907759874830529
952 2561509634915676378730
953 2635831143168520636684
954 2712269972363191536251
955 2790884357092109342731
956 2871736081908377976431
957 2954886635598863346471
958 3040401224088589861058
959 3128344768601442202302
960 3218786082544823585757
961 3311793707394750716585
962 3407440260094381705509
963 3505798100263746782738
964 3606943854899706762314
965 3710953910265200086976
966 3817909120941821220428
967 3927890119498981227613
968 4040982217223882718340
969 4157270524407022977754
970 4276845050358334292845
971 4399795626871697655307
972 4526217215430721267179
973 4656204626130990795184
974 4789858040284851073362
975 4927277516785664776592
976 5068568738638374945806
977 5213837298444663054923
978 5363194677715511910568
979 5516752302839490775883
980 5674627766375368812804
981 5836938644537366228675
982 6003808970020631290620
983 6175362801696800408986
984 6351730958893235602798
985 6533044333639159919410
986 6719440896701537647714
987 6911058742355984306798
988 7108043376878479205453
989 7310540485435686172938
990 7518703514142937426791
991 7732686148275101933539
992 7952650199427925247848
993 8178757783842607331605
994 8411179526650287541046
995 8650086428680570313694
996 8895658400228198663823
997 9148075804277318266925
998 9407528332705894374053
999 9674206213403025364642
1000 9948309442320957052529