1 1
2 2
3 4
4 7
5 11
6 16
7 23
8 33
9 46
10 62
11 83
12 110
13 144
14 186
15 238
16 303
17 383
18 481
19 600
20 744
21 918
22 1128
23 1380
24 1681
25 2039
26 2464
27 2968
28 3563
29 4264
30 5088
31 6054
32 7184
33 8503
34 10040
35 11827
36 13901
37 16304
38 19082
39 22289
40 25986
41 30240
42 35128
43 40736
44 47161
45 54512
46 62911
47 72495
48 83417
49 95850
50 109985
51 126037
52 144246
53 164878
54 188232
55 214639
56 244469
57 278132
58 316084
59 358831
60 406935
61 461020
62 521776
63 589968
64 666442
65 752134
66 848079
67 955420
68 1075419
69 1209468
70 1359103
71 1526016
72 1712071
73 1919321
74 2150024
75 2406664
76 2691971
77 3008945
78 3360879
79 3751389
80 4184442
81 4664388
82 5195993
83 5784481
84 6435572
85 7155525
86 7951191
87 8830061
88 9800324
89 10870928
90 12051648
91 13353156
92 14787100
93 16366187
94 18104275
95 20016472
96 22119240
97 24430513
98 26969819
99 29758416
100 32819436
101 36178040
102 39861589
103 43899824
104 48325065
105 53172420
106 58480014
107 64289234
108 70644996
109 77596029
110 85195181
111 93499752
112 102571847
113 112478761
114 123293391
115 135094676
116 147968078
117 162006089
118 177308785
119 193984414
120 212150032
121 231932187
122 253467648
123 276904193
124 302401450
125 330131806
126 360281373
127 393051034
128 428657556
129 467334789
130 509334949
131 554929992
132 604413088
133 658100199
134 716331770
135 779474536
136 847923463
137 922103821
138 1002473401
139 1089524893
140 1183788424
141 1285834275
142 1396275789
143 1515772474
144 1645033325
145 1784820374
146 1935952480
147 2099309384
148 2275836032
149 2466547203
150 2672532441
151 2894961327
152 3135089104
153 3394262679
154 3673927033
155 3975632053
156 4301039828
157 4651932424
158 5030220178
159 5437950543
160 5877317512
161 6350671672
162 6860530910
163 7409591825
164 8000741887
165 8637072387
166 9321892232
167 10058742633
168 10851412748
169 11703956331
170 12620709457
171 13606309385
172 14665714631
173 15804226327
174 17027510940
175 18341624440
176 19753038003
177 21268665341
178 22895891764
179 24642605071
180 26517228388
181 28528755066
182 30686785768
183 33001567872
184 35484037330
185 38145863135
186 40999494547
187 44058211245
188 47336176577
189 50848494096
190 54611267576
191 58641664709
192 62957984709
193 67579730046
194 72527682558
195 77823984193
196 83492222662
197 89557522275
198 96046640277
199 102988068998
200 110412144152
201 118351159651
202 126839489300
203 135913715779
204 145612767329
205 155978062583
206 167053664020
207 178886440518
208 191526239547
209 205026069540
210 219442293024
211 234834831125
212 251267380093
213 268807640529
214 287527560026
215 307503589993
216 328816957448
217 351553952635
218 375806233340
219 401671146855
220 429252070568
221 458658772221
222 490007790936
223 523422840156
224 559035233730
225 596984336412
226 637418040133
227 680493267466
228 726376503787
229 775244359702
230 827284165415
231 882694598779
232 941686348876
233 1004482817072
234 1071320857580
235 1142451559700
236 1218141073980
237 1298671484699
238 1384341731173
239 1475468580524
240 1572387654692
241 1675454514612
242 1785045804634
243 1901560460419
244 2025420983713
245 2157074787583
246 2296995615876
247 2445685040866
248 2603674043249
249 2771524678861
250 2949831836735
251 3139225093324
252 3340370667988
253 3553973485086
254 3780779348302
255 4021577233113
256 4277201703604
257 4548535460162
258 4836512024905
259 5142118572052
260 5466398910801
261 5810456628673
262 6175458403674
263 6562637494052
264 6973297414862
265 7408815811029
266 7870648537063
267 8360333954116
268 8879497455577
269 9429856232986
270 10013224294617
271 10631517749703
272 11286760371928
273 11981089456468
274 12716761985594
275 13496161118576
276 14321803022415
277 15196344060741
278 16122588359076
279 17103495765543
280 18142190227061
281 19241968602027
282 20406309931538
283 21638885192261
284 22943567555216
285 24324443175890
286 25785822542372
287 27332252409469
288 28968528348142
289 30699707941015
290 32531124656200
291 34468402433250
292 36517471016679
293 38684582074194
294 40976326138592
295 43399650414127
296 45961877490132
297 48670725006725
298 51534326319581
299 54561252212997
300 57760533712833
301 61141686053379
302 64714733854765
303 68490237570235
304 72479321265423
305 76693701794724
306 81145719442928
307 85848370103533
308 90815339068512
309 96061036507854
310 101600634720880
311 107450107245222
312 113626269913361
313 120146823950876
314 127030401214951
315 134296611676322
316 141966093252661
317 150060564106456
318 158602877525717
319 167617079511351
320 177128469200827
321 187163662263776
322 197750657411463
323 208918906168665
324 220699386063363
325 233124677396854
326 246229043764386
327 260048516504301
328 274620983261844
329 289986280862388
330 306186292697770
331 323265050838796
332 341268843096733
333 360246325266836
334 380248638797589
335 401329534140519
336 423545500047023
337 446955899090850
338 471623109707517
339 497612675055222
340 524993459015634
341 553837809667385
342 584221730580179
343 616225060293170
344 649931660357706
345 685429612341699
346 722811424210787
347 762174246520169
348 803620098870504
349 847256107101644
350 893194751719233
351 941554128071398
352 992458218815925
353 1046037179242473
354 1102427636039605
355 1161773000122732
356 1224223794166534
357 1289937995514052
358 1359081395164557
359 1431827973573482
360 1508360294030219
361 1588869914413549
362 1673557818159843
363 1762634865316119
364 1856322264588538
365 1954852067337100
366 2058467684509193
367 2167424427548327
368 2281990074359966
369 2402445461463856
370 2529085103511810
371 2662217841401559
372 2802167520271124
373 2949273698714349
374 3103892390616746
375 3266396841071855
376 3437178337901942
377 3616647060373178
378 3805232966764578
379 4003386722522045
380 4211580670803956
381 4430309847303031
382 4660093041310777
383 4901473905075861
384 5155022113596326
385 5421334577077926
386 5701036708387049
387 5994783747926944
388 6303262148470423
389 6627191022591033
390 6967323655448071
391 7324449085798932
392 7699393758235338
393 8093023249768170
394 8506244074019158
395 8940005566416766
396 9395301853938473
397 9873173913092545
398 10374711719989535
399 10901056496517411
400 11453403056804659
401 12033002258333201
402 12641163562247789
403 13279257707601017
404 13948719504473471
405 14651050751117214
406 15387823280488052
407 16160682141758194
408 16971348922636414
409 17821625218567963
410 18713396255141655
411 19648634670297220
412 20629404463202522
413 21657865116958060
414 22736275902585759
415 23867000372070844
416 25052511048550112
417 26295394322077627
418 27598355559750346
419 28964224439341911
420 30395960515973453
421 31896659031746285
422 33469556978673449
423 35118039425675841
424 36845646120854766
425 38656078380716889
426 40553206278510435
427 42541076144333832
428 44623918390200579
429 46806155673787732
430 49092411415160901
431 51487518681356832
432 53996529454316477
433 56624724298297782
434 59377622443559263
435 62260992303793781
436 65280862445507745
437 68443533028285456
438 71755587735652430
439 75223906217056585
440 78855677062323274
441 82658411330810547
442 86639956658396058
443 90808511966368019
444 95172642797270896
445 99741297303773701
446 104523822917686104
447 109529983727346878
448 114769978592751916
449 120254460028976925
450 125994553889684678
451 132001879883790157
452 138288572959690946
453 144867305592856757
454 151751311014013056
455 158954407416651419
456 166491023184155744
457 174376223178450972
458 182625736133761858
459 191255983200816086
460 200284107688641037
461 209728006052989502
462 219606360182389249
463 229938671034847415
464 240745293680356097
465 252047473806543330
466 263867385747096920
467 276228172094960689
468 289153984964766849
469 302670028971528054
470 316802605995271704
471 331579161804061158
472 347028334610717431
473 363180005641534851
474 380065351798379158
475 397716900498771006
476 416168586781896284
477 435455812771951753
478 455615509593835097
479 476686201839927545
480 498708074690600025
481 521723043795105687
482 545774828023708231
483 570909025206242529
484 597173190976817631
485 624616920849058523
486 653291935651148524
487 683252170454985559
488 714553867139009757
489 747255670729704008
490 781418729672420773
491 817106800188055302
492 854386354878175413
493 893326695747539539
494 934000071819496312
495 976481801526569562
496 1020850400065601391
497 1067187711914162594
498 1115579048712553981
499 1166113332723624409
500 1218883246090832220
501 1273985386123487280
502 1331520426846942404
503 1391593287064667423
504 1454313305188648789
505 1519794421104425130
506 1588155365347307706
507 1659519855876957921
508 1734016802748516040
509 1811780520989910691
510 1892950952006842701
511 1977673893849245124
512 2066101240685790097
513 2158391231846259377
514 2254708710805336434
515 2355225394495631895
516 2460120153352539660
517 2569579302508857564
518 2683796904573014036
519 2802975084441241662
520 2927324356611151396
521 3057063965481909671
522 3192422239144627930
523 3333636957185664023
524 3480955733045332292
525 3634636411495049538
526 3794947481817234084
527 3962168507294352184
528 4136590571636398622
529 4318516742999835879
530 4508262556275629277
531 4706156514349535573
532 4912540609064262263
533 5127770862640548230
534 5352217890342658329
535 5586267485203271327
536 5830321225653309855
537 6084797106933951501
538 6350130197200912160
539 6626773319265147822
540 6915197758949422282
541 7215894001076780349
542 7529372494144895204
543 7856164444779572384
544 8196822643101440900
545 8551922320182095394
546 8922062038809725009
547 9307864618829629524
548 9709978098372038107
549 10129076732328369371
550 10565862029487564093
551 11021063829796446759
552 11495441423262294151
553 11989784712071975686
554 12504915417560250881
555 13041688333720136141
556 13600992629010760591
557 14183753198282896078
558 14790932066709449447
559 15423529847677728436
560 16082587256672321288
561 16769186683252052941
562 17484453823301788732
563 18229559373819944546
564 19005720792585528049
565 19814204125134480248
566 20656325901564114797
567 21533455105776672456
568 22447015219868531905
569 23398486346470561552
570 24389407411947579831
571 25421378453471037692
572 26496062993088974677
573 27615190502031161728
574 28780558958605266710
575 29994037503162004378
576 31257569193733707728
577 32573173866081734002
578 33942951102023752837
579 35369083310052418271
580 36853838922402368252
581 38399575712873098264
582 40008744239871198962
583 41683891419296916667
584 43427664232067181883
585 45242813571240352778
586 47132198233887142788
587 49098789063037755925
588 51145673245227359084
589 53276058769360904005
590 55493279052824206751
591 57800797740981341538
592 60202213686419058739
593 62701266114527352530
594 65301839982241749287
595 68007971537017639904
596 70823854083360323377
597 73753843964496660608
598 76802466767045661697
599 79974423756826262553
600 83274598554231313596
601 86708064057897741743
602 90280089625714305187
603 93996148522530698767
604 97861925644265358193
605 101883325528454538643
606 106066480661642504809
607 110417760094382376155
608 114943778374999747509
609 119651404813667089876
610 124547773088746582896
611 129640291207782907211
612 134936651835966116277
613 140444843005338513099
614 146173159218488994940
615 152130212960964132340
616 158324946637127869731
617 164766644944721743701
618 171464947703915500766
619 178429863157194568096
620 185671781757006616849
621 193201490458685108454
622 201030187536783900569
623 209169497943594405077
624 217631489229276151801
625 226428688043713658789
626 235574097240918007620
627 245081213607521260060
628 254964046237666646483
629 265237135577378149562
630 275915573162300569408
631 287015022073536287904
632 298551738137168679252
633 310542591893955400170
634 323005091366598627690
635 335957405652954718617
636 349418389374533799509
637 363407608010661551342
638 377945364149732056393
639 393052724690073190834
640 408751549024075877789
641 425064518240406804105
642 442015165380332232570
643 459627906785429634251
644 477928074575255390881
645 496941950294872187316
646 516696799773520387458
647 537220909237145169933
648 558543622718967047288
649 580695380813809210399
650 603707760823472586218
651 627613518342080283899
652 652446630331998999378
653 678242339742687776642
654 705037201726626169525
655 732869131508336256256
656 761777453964438138666
657 791802954974668582442
658 822987934605849464785
659 855376262192918901205
660 889013433383335605401
661 923946629213438550357
662 960224777287691776108
663 997898615134170739850
664 1037020755812154517734
665 1077645755850280119021
666 1119830185596393922591
667 1163632702063003642255
668 1209114124355095211878
669 1256337511770035589349
670 1305368244662337843071
671 1356274108169222239464
672 1409125378896169732493
673 1463994914665035710997
674 1520958247430775641556
675 1580093679476434022725
676 1641482382999767627066
677 1705208503208717258068
678 1771359265046913222345
679 1840025083674502574908
680 1911299678833825231186
681 1985280193233845685368
682 2062067315091771903473
683 2141765404974967690031
684 2224482627091094328571
685 2310331085179406592389
686 2399426963161282497562
687 2491890670713390773861
688 2587846993932400480288
689 2687425251265819184933
690 2790759454889415539041
691 2897988477717744964431
692 3009256226240559795811
693 3124711819384354027429
694 3244509773604974463659
695 3368810194424131433069
696 3497778974629770380125
697 3631587999367627906826
698 3770415358358899738233
699 3914445565486801409048
700 4063869786002913236856
701 4218886071612577638106
702 4379699603707267593189
703 4546522945020778883939
704 4719576299995324694736
705 4899087784153138657357
706 5085293702779031094722
707 5278438839229503048599
708 5478776753194513943204
709 5686570089248832045504
710 5902090896041083171702
711 6125620956480163638809
712 6357452129290609905032
713 6597886702320831681984
714 6847237758000829910416
715 7105829551359148631399
716 7373997901022363617991
717 7652090593634404231164
718 7940467802147452324975
719 8239502518451077583454
720 8549581000821667309700
721 8871103236690105754812
722 9204483421242069397303
723 9550150452382246482667
724 9908548442611278435801
725 10280137248382274817778
726 10665393017522390204494
727 11064808755324189165339
728 11478894909931383435957
729 11908179977664023021362
730 12353211128949380553867
731 12814554855546606611059
732 13292797639775774365315
733 13788546646485197046636
734 14302430438514914099533
735 14835099716439025153856
736 15387228083395129288586
737 15959512835835525577058
738 16552675781062075365243
739 17167464082434743751771
740 17804651133172854730133
741 18465037459698039686538
742 19149451655498761558908
743 19858751346528186988807
744 20593824189180087198731
745 21355588901921407014823
746 22144996331695183323799
747 22963030556243653207862
748 23810710023538702989280
749 24689088729545308456804
750 25599257435583340764100
751 26542344926594100149339
752 27519519311660230161427
753 28531989368171299136480
754 29581005931072355136980
755 30667863328679208616441
756 31793900866592118195421
757 32960504361288994981565
758 34169107725030247088972
759 35421194603760007105325
760 36718300069742771399793
761 38062012370730483072031
762 39453974737512863300642
763 40895887251763393769505
764 42389508776154832316088
765 43936658948781563262893
766 45539220243991503140830
767 47199140101797763597439
768 48918433128109879990347
769 50699183368096212221272
770 52543546655063181487295
771 54453753037313392587372
772 56432109285523478112205
773 58481001483263762332100
774 60602897703365655191209
775 62800350772929129138602
776 65076001129851784576564
777 67432579773852956933519
778 69872911315061145744241
779 72399917123330842211690
780 75016618581555687775088
781 77726140446348906213116
782 80531714319569212599640
783 83436682234281013751142
784 86444500358851779414266
785 89558742823007087186766
786 92783105669785136079539
787 96121410937457596024712
788 99577610875612629205056
789 103155792299728902989493
790 106860181088706536253277
791 110695146829962307368946
792 114665207616842233397704
793 118775035003254940117585
794 123029459120584219641246
795 127433473962098958787221
796 131992242840243363618280
797 136711104022360254578468
798 141595576550575317889495
799 146651366251750732396735
800 151884371943602711757404
801 157300691843269379533569
802 162906630184813204253251
803 168708704052346142912501
804 174713650435675860157372
805 180928433515588097480492
806 187360252186103658853497
807 194016547821278758808984
808 200905012294354854624265
809 208033596257308770685596
810 215410517689106141449801
811 223044270721221177363000
812 230943634749253730096729
813 239117683839750840930659
814 247575796441624647619566
815 256327665411851956570059
816 265383308365443222143398
817 274753078359980384722338
818 284447674925344283191294
819 294478155449583463304165
820 304855946932217447181616
821 315592858116619215770414
822 326701092013484099398410
823 338193258827765794724423
824 350082389301845162103168
825 362381948488094148164831
826 375105849964405976847225
827 388268470506684021205364
828 401884665232715881738650
829 415969783232306539398996
830 430539683699005418870848
831 445610752579237197787759
832 461199919755135649892241
833 477324676777884146705602
834 494003095168886107684500
835 511253845306624140781750
836 529096215917618324906167
837 547550134190462537907117
838 566636186532503427520858
839 586375639989330071953104
840 606790464347864110220298
841 627903354944480684287436
842 649737756200250485596215
843 672317885906073114321012
844 695668760281172434013302
845 719816219829146247916873
846 744786956016506064700933
847 770608538799408607546360
848 797309445025069717174197
849 824919087735164091669424
850 853467846399351598929284
851 882987098107933416885226
852 913509249753529749058476
853 945067771232586096979244
854 977697229698457837337361
855 1011433324898793964225899
856 1046312925630941152912492
857 1082374107350119642959162
858 1119656190966183711947387
859 1158199782865872629004329
860 1198046816198583878671221
861 1239240593464860096511374
862 1281825830447975552305849
863 1325848701530238177585836
864 1371356886436890114050419
865 1418399618451794640998318
866 1467027734150441237442230
867 1517293724697184594441567
868 1569251788755058794852025
869 1622957887057975834657001
870 1678469798696629420831197
871 1735847179170981829803849
872 1795151620263814869569648
873 1856446711791477016938434
874 1919798105289658998063886
875 1985273579693780884243043
876 2052943109075376666419987
877 2122878932497718773807254
878 2195155626055836681270257
879 2269850177168052218316184
880 2347042061188181107672999
881 2426813320409637329096082
882 2509248645534825878677704
883 2594435459685422180333131
884 2682464005031414660786608
885 2773427432119132731941819
886 2867421891980897599323908
887 2964546631111419952859430
888 3064904089398628774939849
889 3168600001099251358228443
890 3275743498952178360836429
891 3386447221525441600925571
892 3500827423895508632665483
893 3619004091760559343330200
894 3741101059092458327939671
895 3867246129435275164163605
896 3997571200961435529245573
897 4132212395399912049644687
898 4271310190954287606308289
899 4415009559332048365699781
900 4563460107010091981160581
901 4716816220865171205916603
902 4875237218301837658176688
903 5038887502014407847915616
904 5207936719523547071606013
905 5382559927632259755305167
906 5562937761950390723061344
907 5749256611641184229178785
908 5941708799548020062444033
909 6140492767864152354111460
910 6345813269513120751458144
911 6557881565412489316226928
912 6776915627798699945486885
913 7003140349796108479698845
914 7236787761418707265767855
915 7478097252198632209910934
916 7727315800641309839590371
917 7984698210713025277359231
918 8250507355572790126076390
919 8525014428766665024115291
920 8808499203109150139919237
921 9101250297482903369879830
922 9403565451794885861664440
923 9715751810334073237798160
924 10038126213783114228083196
925 10371015500143772180746801
926 10714756814843655121765091
927 11069697930299632849155678
928 11436197575221461337195418
929 11814625773947492015805369
930 12205364196112942997254066
931 12608806516960057948612231
932 13025358788608583150235975
933 13455439822614361632920462
934 13899481584153482648456220
935 14357929598179342809209238
936 14831243367910179956752049
937 15319896806015140333791878
938 15824378678877742311639340
939 16345193064326714375130503
940 16882859823235620136504136
941 17437915085404447934447057
942 18010911750148446423289557
943 18602420002031940079790706
944 19213027842197669628575301
945 19843341635755382164732556
946 20493986675706954668750737
947 21165607763899283390702039
948 21858869809510521251691093
949 22574458445590007301910845
950 23313080664187418032058617
951 24075465470622291927787348
952 24862364557461148387167034
953 25674552998785952632185152
954 26512829965354682531334610
955 27378019461272244665947575
956 28270971082807979243001728
957 29192560800014500686861265
958 30143691761821657427735433
959 31125295125298975442813005
960 32138330909800090806616058
961 33183788876723392603172041
962 34262689435644405212221901
963 35376084577597354819819757
964 36525058836305906094304655
965 37710730278186238857191856
966 38934251521969479294788181
967 40196810788815024327474767
968 41499632983811520217756790
969 42843980809788196918294469
970 44231155914385938139180710
971 45662500071364904305343544
972 47139396397153742704399458
973 48663270603674438000888853
974 50235592288506699322768175
975 51857876263486470334586808
976 53531683922864709755967255
977 55258624652185045970723303
978 57040357279072285675505929
979 58878591567158078597027536
980 60775089754405334527410743
981 62731668137129282374729692
982 64750198701050381429517969
983 66832610800752671199555462
984 68980892888960607339307622
985 71197094297088007575807298
986 73483327068554454114174291
987 75841767846407399646025876
988 78274659816832335506260616
989 80784314710178736345894168
990 83373114861176130446909176
991 86043515330062593978576603
992 88798046086397267530876632
993 91639314257379181601300226
994 94570006442546792819287644
995 97592891096786214079127477
996 100710820983631210005117347
997 103926735700894665985403530
998 107243664280729467211432057
999 110664727866276587742055177
1000 114193142467119733765382433