1 1
2 2
3 3
4 5
5 8
6 12
7 17
8 24
9 34
10 48
11 67
12 92
13 124
14 164
15 213
16 273
17 347
18 439
19 554
20 698
21 878
22 1102
23 1379
24 1719
25 2133
26 2633
27 3232
28 3944
29 4784
30 5768
31 6913
32 8238
33 9765
34 11520
35 13534
36 15844
37 18494
38 21536
39 25031
40 29050
41 33675
42 39000
43 45132
44 52192
45 60316
46 69656
47 80381
48 92678
49 106753
50 122832
51 141162
52 162012
53 185674
54 212464
55 242723
56 276818
57 315143
58 358120
59 406200
60 459864
61 519624
62 586024
63 659641
64 741087
65 831012
66 930108
67 1039114
68 1158822
69 1290084
70 1433820
71 1591027
72 1762789
73 1950288
74 2154816
75 2377788
76 2620756
77 2885424
78 3173664
79 3487533
80 3829291
81 4201420
82 4606644
83 5047950
84 5528610
85 6052204
86 6622644
87 7244199
88 7921521
89 8659672
90 9464152
91 10340928
92 11296464
93 12337752
94 13472344
95 14708385
96 16054647
97 17520564
98 19116268
99 20852626
100 22741278
101 24794676
102 27026124
103 29449819
104 32080893
105 34935456
106 38030640
107 41384644
108 45016780
109 48947520
110 53198544
111 57792789
112 62754499
113 68109276
114 73884132
115 80107542
116 86809498
117 94021564
118 101776932
119 110110479
120 119058825
121 128660392
122 138955464
123 149986248
124 161796936
125 174433768
126 187945096
127 202381449
128 217795600
129 234242636
130 251780032
131 270467730
132 290368224
133 311546652
134 334070896
135 358011691
136 383442744
137 410440864
138 439086104
139 469461916
140 501655320
141 535757088
142 571861944
143 610068781
144 650480896
145 693206244
146 738357712
147 786053414
148 836417008
149 889578036
150 945672288
151 1004842191
152 1067237224
153 1133014360
154 1202338536
155 1275383152
156 1352330600
157 1433372824
158 1518711912
159 1608560721
160 1703143536
161 1802696764
162 1907469664
163 2017725114
164 2133740416
165 2255808140
166 2384237008
167 2519352819
168 2661499416
169 2811039696
170 2968356664
171 3133854532
172 3307959864
173 3491122768
174 3683818136
175 3886546933
176 4099837536
177 4324247124
178 4560363120
179 4808804686
180 5070224272
181 5345309220
182 5634783424
183 5939409047
184 6259988296
185 6597365256
186 6952427784
187 7326109464
188 7719391624
189 8133305416
190 8568933960
191 9027414553
192 9509940944
193 10017765676
194 10552202496
195 11114628834
196 11706488352
197 12329293564
198 12984628528
199 13674151611
200 14399598328
201 15162784256
202 15965608024
203 16810054380
204 17698197336
205 18632203392
206 19614334840
207 20646953149
208 21732522432
209 22873612996
210 24072904976
211 25333192054
212 26657385264
213 28048516884
214 29509744416
215 31044354655
216 32655767848
217 34347541944
218 36123376936
219 37987119296
220 39942766504
221 41994471672
222 44146548264
223 46403474913
224 48769900336
225 51250648348
226 53850722976
227 56575313674
228 59429800640
229 62419760236
230 65550970512
231 68829416835
232 72261297624
233 75853030192
234 79611256696
235 83542850196
236 87654920824
237 91954822064
238 96450157144
239 101148785541
240 106058829600
241 111188681268
242 116547008944
243 122142764446
244 127985190096
245 134083825924
246 140448516992
247 147089420839
248 154017015048
249 161242104936
250 168775831368
251 176629678696
252 184815482824
253 193345439400
254 202232112136
255 211488441257
256 221127752081
257 231163763733
258 241610597997
259 252482788311
260 263795288911
261 275563484131
262 287803197867
263 300530703214
264 313762732286
265 327516486230
266 341809645446
267 356660380026
268 372087360426
269 388109768386
270 404747308114
271 422020217751
272 439949281135
273 458555839883
274 477861805811
275 497889673713
276 518662534521
277 540204088869
278 562538661085
279 585691213636
280 609687362052
281 634553390356
282 660316267028
283 687003661532
284 714643961436
285 743266290156
286 772900525356
287 803577318037
288 835328112349
289 868185166161
290 902181572425
291 937351281371
292 973729123571
293 1011350833911
294 1050253076511
295 1090473470634
296 1132050617626
297 1175024128930
298 1219434655218
299 1265323916686
300 1312734734558
301 1361711063846
302 1412298027414
303 1464541951395
304 1518490402011
305 1574192223847
306 1631697579631
307 1691057991573
308 1752326384317
309 1815557129561
310 1880806092401
311 1948130679456
312 2017589888832
313 2089244361984
314 2163156437536
315 2239390207120
316 2318011573296
317 2399088309616
318 2482690122896
319 2568888717761
320 2657757863529
321 2749373463501
322 2843813626725
323 2941158742303
324 3041491556311
325 3144897251403
326 3251463529171
327 3361280695334
328 3474441747830
329 3591042467886
330 3711181514142
331 3834960519906
332 3962484193618
333 4093860422602
334 4229200380186
335 4368618636271
336 4512233271431
337 4660165994627
338 4812542264619
339 4969491415161
340 5131146784065
341 5297645846221
342 5469130350661
343 5645746461756
344 5827644904636
345 6014981114924
346 6207915392876
347 6406613062020
348 6611244632388
349 6821985968436
350 7039018461748
351 7262529208621
352 7492711192629
353 7729763472265
354 7973891373761
355 8225306689187
356 8484227879931
357 8750880285663
358 9025496338887
359 9308315785186
360 9599585909266
361 9899561766906
362 10208506422922
363 10526691195254
364 10854395905286
365 11191909134510
366 11539528487646
367 11897560862331
368 12266322725491
369 12646140396511
370 13037350337319
371 13440299449501
372 13855345378565
373 14282856825473
374 14723213865561
375 15176808274968
376 15644043864696
377 16125336822424
378 16621116062200
379 17131823582136
380 17657914830232
381 18199859078456
382 18758139805208
383 19333255086297
384 19925717994561
385 20536057008261
386 21164816428381
387 21812556804967
388 22479855372639
389 23167306495411
390 23875522120955
391 24605132244446
392 25356785382126
393 26131149054726
394 26928910280886
395 27750776080714
396 28597473989626
397 29469752582610
398 30368382009058
399 31294154538311
400 32247885116063
401 33230411931771
402 34242596997219
403 35285326736385
404 36359512586761
405 37466091612277
406 38606027127981
407 39780309336628
408 40989955977332
409 42236012986436
410 43519555170756
411 44841686893356
412 46203542772012
413 47606288390524
414 49051121023036
415 50539270371525
416 52071999316621
417 53650604681921
418 55276418011961
419 56950806364011
420 58675173113859
421 60450958775751
422 62279641836655
423 64162739605018
424 66101809074186
425 68098447800658
426 70154294797346
427 72271031442014
428 74450382401070
429 76694116568886
430 79004048022822
431 81382036994131
432 83829990854923
433 86349865121367
434 88943664473311
435 91613443790501
436 94361309205581
437 97189419174057
438 100099985561409
439 103095274747536
440 106177608748720
441 109349366357296
442 112612984299216
443 115970958409696
444 119425844827136
445 122980261205504
446 126636887945376
447 130398469443825
448 134267815363353
449 138247801920061
450 142341373191253
451 146551542442671
452 150881393475559
453 155334081993755
454 159912836991011
455 164620962158742
456 169461837314406
457 174438919850718
458 179555746205902
459 184815933355186
460 190223180323746
461 195781269721306
462 201494069298602
463 207365533525919
464 213399705193911
465 219600717036915
466 225972793378971
467 232520251802761
468 239247504841681
469 246159061695261
470 253259529968149
471 260553617432876
472 268046133816620
473 275741992612188
474 283646212913436
475 291763921275348
476 300100353598996
477 308660857041604
478 317450891951940
479 326476033831261
480 335741975320037
481 345254528210681
482 355019625486513
483 365043323387187
484 375331803500811
485 385891374882991
486 396728476203031
487 407849677917522
488 419261684471554
489 430971336527786
490 442985613223610
491 455311634456646
492 467956663198806
493 480928107839166
494 494233524555886
495 507880619717419
496 521877252313251
497 536231436414415
498 550951343664023
499 566045305798061
500 581521817196693
501 597389537466321
502 613657294052649
503 630334084885000
504 647429081052136
505 664951629509832
506 682911255820456
507 701317666924808
508 720180753946472
509 739510595028936
510 759317458205736
511 779611804303881
512 800404289880818
513 821705770195199
514 843527302211716
515 865880147640275
516 888775776009786
517 912225867776853
518 936242317469656
519 960837236867326
520 986022958215124
521 1011812037475746
522 1038217257617088
523 1065251631936818
524 1092928407424116
525 1121261068158958
526 1150263338749336
527 1179949187806823
528 1210332831460910
529 1241428736912561
530 1273251626027452
531 1305816478969381
532 1339138537874358
533 1373233310565907
534 1408116574312136
535 1443804379625156
536 1480313054103456
537 1517659206317868
538 1555859729741784
539 1594931806726316
540 1634892912521120
541 1675760819341636
542 1717553600483528
543 1760289634485141
544 1803987609338826
545 1848666526752019
546 1894345706458996
547 1941044790584263
548 1988783748058578
549 2037582879088641
550 2087462819681528
551 2138444546224986
552 2190549380124748
553 2243798992500070
554 2298215408938736
555 2353821014312822
556 2410638557656556
557 2468691157107658
558 2528002304913592
559 2588595872504211
560 2650496115632326
561 2713727679583781
562 2778315604458668
563 2844285330525369
564 2911662703649166
565 2980473980797215
566 3050745835621736
567 3122505364123328
568 3195780090396376
569 3270597972458576
570 3346987408166664
571 3424977241220496
572 3504596767257688
573 3585875740041088
574 3668844377741416
575 3753533369317473
576 3839973880996386
577 3928197562856423
578 4018236555514980
579 4110123496924411
580 4203891529278442
581 4299574306031981
582 4397205999037208
583 4496821305798902
584 4598455456852036
585 4702144223264746
586 4807923924269856
587 4915831435028218
588 5025904194527204
589 5138180213617766
590 5252698083193560
591 5369496982515711
592 5488616687686878
593 5610097580278361
594 5733980656114076
595 5860307534215309
596 5989120465910246
597 6120462344112363
598 6254376712771848
599 6390907776504316
600 6530100410401168
601 6672000170026036
602 6816653301601848
603 6964106752393140
604 7114408181288336
605 7267605969586812
606 7423749231995656
607 7582887827841133
608 7745072372499962
609 7910354249055611
610 8078785620184916
611 8250419440280431
612 8425309467814018
613 8603510277947289
614 8785077275394616
615 8970066707544530
616 9158535677845436
617 9350542159461678
618 9546145009206096
619 9745403981755326
620 9948379744154204
621 10155133890615746
622 10365728957623288
623 10580228439341483
624 10798696803342966
625 11021199506657613
626 11247803012151436
627 11478574805242273
628 11713583410959550
629 11952898411355511
630 12196590463275432
631 12444731316494456
632 12697393832228808
633 12954652002029272
634 13216580967064936
635 13483257037805336
636 13754757714109256
637 14031161705728568
638 14312548953235624
639 14599000649382841
640 14890599260903250
641 15187428550760911
642 15489573600860228
643 15797120835223331
644 16110158043644826
645 16428774405833349
646 16753060516049496
647 17083108408249838
648 17419011581746868
649 17760865027394866
650 18108765254311808
651 18462810317147586
652 18823099843908948
653 19189735064351710
654 19562818838950936
655 19942455688459927
656 20328751824069006
657 20721815178175233
658 21121755435774332
659 21528684066486261
660 21942714357226006
661 22363961445531331
662 22792542353559368
663 23228576022764084
664 23672183349266816
665 24123487219932220
666 24582612549162136
667 25049686316420028
668 25524837604498816
669 26008197638545076
670 26499899825852744
671 27000079796439621
672 27508875444420138
673 28026426970188003
674 28552876923422516
675 29088370246932503
676 29633054321351986
677 30187079010701873
678 30750596708832120
679 31323762386758986
680 31906733640912172
681 32499670742306806
682 33102736686655408
683 33716097245435142
684 34339921017925836
685 34974379484234426
686 35619647059321656
687 36275901148047043
688 36943322201248294
689 37622093772871541
690 38312402578168940
691 39014438552980361
692 39728394914116078
693 40454468220857551
694 41192858437593576
695 41943768997609264
696 42707406868045496
697 43483982616046688
698 44273710476114888
699 45076808418688416
700 45893498219963448
701 46724005532977136
702 47568559959971048
703 48427395126053905
704 49300748754182786
705 50188862741482167
706 51091983236920356
707 52010360720363083
708 52944250083024202
709 53893910709333661
710 54859606560243096
711 55841606257989606
712 56840183172338468
713 57855615508325754
714 58888186395522016
715 59938183978838410
716 61005901510896836
717 62091637445985878
718 63195695535624536
719 64318384925755951
720 65460020255593534
721 66620921758142121
722 67801415362416988
723 69001832797383773
724 70222511697642566
725 71463795710879643
726 72726034607110536
727 74009584389738348
728 75314807408451440
729 76642072473984836
730 77991754974769912
731 79364236995497156
732 80759907437617008
733 82179162141804012
734 83622404012409736
735 85090043143930141
736 86582496949513306
737 88100190291533643
738 89643555614258964
739 91213033078636991
740 92809070699228130
741 94432124483311561
742 96082658572191928
743 97761145384734146
744 99468065763154076
745 101203909121093054
746 102969173594004496
747 104764366191881038
748 106590002954350908
749 108446609108172466
750 110334719227156088
751 112254877394542811
752 114207637367869398
753 116193562746349725
754 118213227140802636
755 120267214346156657
756 122356118516562206
757 124480544343142183
758 126641107234412072
759 128838433499400936
760 131073160533504936
761 133345937007105256
762 135657423056982568
763 138008290480560424
764 140399222933010216
765 142830916127250600
766 145304078036874536
767 147819429102037353
768 150377702438339506
769 152979644048737951
770 155626013038520324
771 158317581833376371
772 161055136400601338
773 163839476473466293
774 166671415778790616
775 169551782267752158
776 172481418349970836
777 175461181130901698
778 178491942652573760
779 181574590137711186
780 184710026237273652
781 187899169281453006
782 191142953534163608
783 194442329451064007
784 197798263941147886
785 201211740631942481
786 204683760138352956
787 208215340335191493
788 211807516633430134
789 215461342260216691
790 219177888542693320
791 222958245195657636
792 226803520613106528
793 230714842163703116
794 234693356490207576
795 238740229812912844
796 242856648237126496
797 247043818064740388
798 251302966109929928
799 255635340019025141
800 260042208594595978
801 264524862123794611
802 269084612710997748
803 273722794614792295
804 278440764589347986
805 283239902230220897
806 288121610324632056
807 293087315206265658
808 298138467114631692
809 303276540559038086
810 308503034687217776
811 313819473658656406
812 319227407022666668
813 324728410101255594
814 330324084376831416
815 336016057884796915
816 341805985611076486
817 347695549894624453
818 353686460834962476
819 359780456704794201
820 365979304367745614
821 372284799701279871
822 378698768024835688
823 385223064533238688
824 391859574735435416
825 398610214898600048
826 405476932497664136
827 412461706670320048
828 419566548677549080
829 426793502369725536
830 434144644658348392
831 441622085993452481
832 449227970846751458
833 456964478200565127
834 464833822042584036
835 472838251866524571
836 480980053178728106
837 489261548010758093
838 497685095438049304
839 506253092104663766
840 514967972754208260
841 523832210766968586
842 532848318703316128
843 542018848853442586
844 551346393793479076
845 560833586948056134
846 570483103159361496
847 580297659262752863
848 590280014668983198
849 600432971953096441
850 610759377450051868
851 621262121857135661
852 631944140843218598
853 642808415664919115
854 653857973789731336
855 665095889526178012
856 676525284661048656
857 688149329103783508
858 699971241538064312
859 711994290080673236
860 724221792947681616
861 736657119128030556
862 749303689064565768
863 762164975342589389
864 775244503385991866
865 788545852161027355
866 802072654887796436
867 815828599759500303
868 829817430669530946
869 844042947946462201
870 858509009097006904
871 873219529557005746
872 888178483450513788
873 903389904357050958
874 918857886087083216
875 934586583465801438
876 950580213125265436
877 966843054304980898
878 983379449660977400
879 1000193806083456011
880 1017290595523075382
881 1034674355825945581
882 1052349691577399308
883 1070321274954610497
884 1088593846588130686
885 1107172216432413911
886 1126061264645401256
887 1145265942477236568
888 1164791273168185224
889 1184642352855828216
890 1204824351491604200
891 1225342513766772536
892 1246202160047870728
893 1267408687321740056
894 1288967570150193576
895 1310884361634401049
896 1333164694389065746
897 1355814281526468463
898 1378838917650454468
899 1402244479860439491
900 1426036928765511258
901 1450222309508703461
902 1474806752801519448
903 1499796475968783310
904 1525197784003896436
905 1551017070634578002
906 1577260819399168256
907 1603935604733573858
908 1631048093068934932
909 1658605043940093886
910 1686613311104946456
911 1715079843674755831
912 1744011687255511118
913 1773415985100411809
914 1803299979273560316
915 1833671011824945045
916 1864536525976796886
917 1895904067321402403
918 1927781285030457416
919 1960175933076045076
920 1993095871463322944
921 2026549067475003996
922 2060543596927716888
923 2095087645440331228
924 2130189509714334016
925 2165857598826343828
926 2202100435532849736
927 2238926657587262373
928 2276345019069364970
929 2314364391727252611
930 2352993766331848372
931 2392242254044085431
932 2432119087794844658
933 2472633623677737617
934 2513795342354825336
935 2555613850475363626
936 2598098882107666156
937 2641260300184176918
938 2685108097959844144
939 2729652400483888166
940 2774903466085056140
941 2820871687870456986
942 2867567595238070328
943 2915001855403023651
944 2963185274937732326
945 3012128801325997589
946 3061843524531157996
947 3112340678578390313
948 3163631643151256238
949 3215727945202591791
950 3268641260579836648
951 3322383415664901136
952 3376966389028669048
953 3432402313100234880
954 3488703475850974536
955 3545882322493548992
956 3603951457195940856
957 3662923644810624208
958 3722811812618968552
959 3783629052090978161
960 3845388620660468546
961 3908103943515782231
962 3971788615406146468
963 4036456402463775979
964 4102121244041824266
965 4168797254568287485
966 4236498725415965336
967 4305240126788583878
968 4375036109623185636
969 4445901507508892826
970 4517851338622149984
971 4590900807678552746
972 4665065307901369988
973 4740360423006866998
974 4816801929206537816
975 4894405797226355343
976 4973188194343148286
977 5053165486438214473
978 5134354240068280540
979 5216771224553918461
980 5300433414085529862
981 5385357989847009531
982 5471562342157200008
983 5559064072629249612
984 5647880996347986736
985 5738031144065423716
986 5829532764414504056
987 5922404326141207268
988 6016664520355126064
989 6112332262798631116
990 6209426696134739080
991 6307967192253800061
992 6407973354599121178
993 6509465020511643371
994 6612462263593789076
995 6716985396092598879
996 6823054971302275746
997 6930691785986255913
998 7039916882818926008
999 7150751552847106466
1000 7263217337971421788