0 1
1 1
2 2
3 3
4 5
5 7
6 10
7 14
8 19
9 26
10 35
11 46
12 61
13 79
14 102
15 131
16 167
17 211
18 266
19 333
20 415
21 515
22 636
23 782
24 959
25 1171
26 1425
27 1729
28 2091
29 2521
30 3033
31 3637
32 4351
33 5193
34 6183
35 7345
36 8708
37 10301
38 12161
39 14331
40 16856
41 19789
42 23195
43 27139
44 31703
45 36978
46 43063
47 50075
48 58148
49 67426
50 78079
51 90298
52 104294
53 120308
54 138617
55 159520
56 183364
57 210538
58 241472
59 276654
60 316636
61 362022
62 413502
63 471846
64 537907
65 612645
66 697136
67 792568
68 900277
69 1021754
70 1158648
71 1312802
72 1486277
73 1681341
74 1900536
75 2146683
76 2422899
77 2732657
78 3079813
79 3468621
80 3903812
81 4390625
82 4934843
83 5542875
84 6221820
85 6979492
86 7824549
87 8766553
88 9816034
89 10984628
90 12285176
91 13731796
92 15340076
93 17127182
94 19111986
95 21315276
96 23759929
97 26471061
98 29476310
99 32806045
100 36493585
101 40575533
102 45092078
103 50087255
104 55609399
105 61711499
106 68451579
107 75893241
108 84106146
109 93166498
110 103157739
111 114171154
112 126306530
113 139672994
114 154389837
115 170587318
116 188407767
117 208006599
118 229553392
119 253233244
120 279248092
121 307818077
122 339183277
123 373605359
124 411369368
125 452785854
126 498193025
127 547958987
128 602484456
129 662205452
130 727596184
131 799172414
132 877494915
133 963173081
134 1056869198
135 1159302751
136 1271255048
137 1393574523
138 1527182201
139 1673077505
140 1832344910
141 2006160784
142 2195800749
143 2402647930
144 2628201613
145 2874086409
146 3142062622
147 3434037029
148 3752074420
149 4098410473
150 4475465259
151 4885857647
152 5332421364
153 5818221794
154 6346574028
155 6921062736
156 7545563175
157 8224263605
158 8961690014
159 9762732183
160 10632671612
161 11577212106
162 12602512197
163 13715219742
164 14922509855
165 16232124997
166 17652417944
167 19192398592
168 20861783632
169 22671049656
170 24631490977
171 26755280942
172 29055537617
173 31546394965
174 34243078588
175 37161986633
176 40320777518
177 43738463148
178 47435508633
179 51433940082
180 55757459311
181 60431566423
182 65483692244
183 70943339127
184 76842231610
185 83214478682
186 90096746645
187 97528443760
188 105551919091
189 114212674187
190 123559589287
191 133645166499
192 144525788867
193 156261996953
194 168918786068
195 182565922693
196 197278282474
197 213136212828
198 230225919211
199 248639877380
200 268477275466
201 289844484699
202 312855561881
203 337632787481
204 364307238863
205 393019401665
206 423919824342
207 457169815095
208 492942185193
209 531422043998
210 572807645542
211 617311291005
212 665160293546
213 716598005256
214 771884911929
215 831299802334
216 895141012984
217 963727754316
218 1037401526605
219 1116527626758
220 1201496753362
221 1292726719196
222 1390664273531
223 1495787042362
224 1608605597806
225 1729665659292
226 1859550436923
227 1998883129184
228 2148329579500
229 2308601103178
230 2480457499401
231 2664710253788
232 2862225945612
233 3073929876066
234 3300809925575
235 3543920655910
236 3804387677022
237 4083412287996
238 4382276411435
239 4702347843762
240 5045085834029
241 5412047013387
242 5804891702047
243 6225390608751
244 6675431949747
245 7157029017529
246 7672328219164
247 8223617614965
248 8813335993695
249 9444082508035
250 10118626907147
251 10839920408050
252 11611107235572
253 12435536873470
254 13316777076427
255 14258627678125
256 15265135246805
257 16340608645201
258 17489635538782
259 18717099911860
260 20028200658918
261 21428471303654
262 22923800916559
263 24520456309008
264 26225105568203
265 28044843015157
266 29987215678280
267 32060251358658
268 34272488384888
269 36633007164788
270 39151463626211
271 41838124661177
272 44703905699949
273 47760410524258
274 51019973455253
275 54495704063036
276 58201534529659
277 62152269823497
278 66363640858218
279 70852360792366
280 75636184655999
281 80733972506383
282 86165756299192
283 91952810692980
284 98117728024862
285 104684497677051
286 111678590091672
287 119127045710665
288 127058569102599
289 135503628577143
290 144494561612270
291 154065686403044
292 164253419885733
293 175096402616385
294 186635630870326
295 198914596375510
296 211979434125183
297 225879078700405
298 240665429588011
299 256393526013420
300 273121731797136
301 290911930802420
302 309829733582641
303 329944695825933
304 351330549263111
305 374065445748115
306 398232215215922
307 423918638295080
308 451217734405275
309 480228066166580
310 511054061030617
311 543806351102063
312 578602132122311
313 615565542677375
314 654828064762618
315 696528946841653
316 740815650642606
317 787844323010998
318 837780294153918
319 890798603725300
320 947084556292548
321 1006834307745722
322 1070255484342671
323 1137567836184072
324 1209003926946824
325 1284809861848435
326 1365246055935857
327 1450588044833222
328 1541127340250678
329 1637172332690766
330 1739049243847218
331 1847103131377112
332 1961698948884934
333 2083222664028461
334 2212082437871054
335 2348709868781281
336 2493561304276691
337 2647119224446012
338 2809893700792293
339 2982423934453782
340 3165279878032912
341 3359063945499359
342 3564412814778034
343 3781999327938889
344 4012534494181763
345 4256769600980310
346 4515498439103130
347 4789559647541786
348 5079839184588509
349 5387272931703910
350 5712849437178143
351 6057612806841402
352 6422665749536189
353 6809172785476936
354 7218363625930737
355 7651536733166373
356 8110063070101701
357 8595390049439198
358 9109045692671639
359 9652643009889530
360 10227884611754436
361 10836567565673271
362 11480588508845588
363 12161949031362590
364 12882761343308313
365 13645254240539328
366 14451779384425057
367 15304817911703743
368 16206987391452104
369 17161049146872183
370 18169915960602275
371 19236660183222980
372 20364522265462822
373 21556919735748487
374 22817456645860506
375 24149933508423304
376 25558357751270798
377 27046954715003071
378 28620179221189265
379 30282727740164927
380 32039551188843640
381 33895868390286162
382 35857180228483845
383 37929284533497573
384 40118291733642911
385 42430641313362861
386 44873119117375284
387 47452875543473675
388 50177444668600675
389 53054764355040786
390 56093197385666326
391 59301553679727892
392 62689113643244484
393 66265652710462450
394 70041467135786470
395 74027401098519686
396 78234875185557541
397 82675916320525189
398 87363189211226786
399 92310029390513739
400 97530477929514574
401 103039317906038427
402 108852112714715031
403 114985246309813944
404 121455965476133729
405 128282424227672629
406 135483730438814035
407 143079994817848947
408 151092382337654047
409 159543166244077555
410 168455784768428363
411 177854900676215042
412 187766463790846797
413 198217776637695985
414 209237563360556683
415 220856042070029181
416 233105000791035464
417 246017877184293428
418 259629842225159489
419 273977888032028938
420 289100920045259658
421 305039853767386150
422 321837716285452060
423 339539752806365452
424 358193538447394960
425 377849095535427164
426 398559016680193025
427 420378593899469542
428 443365954087438042
429 467582201130667643
430 493091564990824472
431 519961558088267825
432 548263139335945176
433 578070886189699569
434 609463175098336485
435 642522370754266250
436 677335024564625798
437 713992082782466029
438 752589104757622091
439 793226491788660692
440 836009727079802139
441 881049627329641738
442 928462606503361095
443 978370952365813537
444 1030903116379122746
445 1086194017596791108
446 1144385361215671916
447 1205625972477176329
448 1270072146641451401
449 1337888015791763646
450 1409245933260657159
451 1484326876506354100
452 1563320869306104785
453 1646427424172419911
454 1733856005940203552
455 1825826517516410283
456 1922569808828677904
457 2024328210057337777
458 2131356090284950994
459 2243920442748687288
460 2362301497935518006
461 2486793365816894302
462 2617704708577993751
463 2755359445258865675
464 2900097489789441495
465 3052275523966994368
466 3212267806995545221
467 3380467023280329135
468 3557285170246424782
469 3743154488031367452
470 3938528432985427063
471 4143882696999835496
472 4359716274775136021
473 4586552581237291665
474 4824940621407885435
475 5075456215139282132
476 5338703279234301069
477 5615315169582337492
478 5905956086062809022
479 6211322543090441292
480 6532144908804884027
481 6869189016042391154
482 7223257848367948739
483 7595193304591867803
484 7985878045348635697
485 8396237425475729552
486 8827241516095806500
487 9279907220480434637
488 9755300487955329942
489 10254538630295501453
490 10778792745257280574
491 11329290252100789769
492 11907317544170651394
493 12514222763828275278
494 13151418705263768828
495 13820385850958969227
496 14522675547829238480
497 15259913329338183179
498 16033802390156071842
499 16846127220223476949
500 17698757405384281352
501 18593651602066311738
502 19532861693817857581
503 20518537137851774613
504 21552929510105520322
505 22638397257699844045
506 23777410668068568459
507 24972557064436635053
508 26226546237748248885
509 27542216125588983711
510 28922538749104926229
511 30370626419403447178
512 31889738225421449601
513 33483286815767756508
514 35154845487592161372
515 36908155596101877377
516 38747134298936661389
517 40675882650232459522
518 42698694059847402605
519 44820063133893304228
520 47044694913416645016
521 49377514528802605615
522 51823677288234150239
523 54388579219331910634
524 57077868083926991441
525 59897454886777908840
526 62853525899941673556
527 65952555225444688222
528 69201317919872007532
529 72606903705510901436
530 76176731293743828880
531 79918563347487267244
532 83840522110624213947
533 87951105733576752095
534 92259205325411519472
535 96774122764173485128
536 101505589298499459007
537 106463784974972938006
538 111659358927155179560
539 117103450563761026325
540 122807711695043034032
541 128784329638113306897
542 135046051343666535512
543 141606208588371249813
544 148478744279079437790
545 155678239916964812025
546 163219944271738758041
547 171119803318221096964
548 179394491489757908383
549 188061444305282580411
550 197138892429220612299
551 206645897225941190572
552 216602387873061479793
553 227029200100625241789
554 237948116626003864909
555 249381909357307702228
556 261354383441162180412
557 273890423233894561104
558 287016040278496732073
559 300758423373191176008
560 315145990821029883361
561 330208444953703066252
562 345976829026641487437
563 362483586586561847996
564 379762623416833371754
565 397849372170451868340
566 416780859804994583942
567 436595777938699948090
568 457334556251788754859
569 479039439062317133946
570 501754565211232726859
571 525526051396912877605
572 550402079105297878395
573 576432985287799989600
574 603671356945490846822
575 632172129784647004805
576 661992691115573574507
577 693192987173751398422
578 725835635049766050228
579 759986039422185896826
580 795712514295585754024
581 833086409954265145089
582 872182245350896045128
583 913077846158380333806
584 955854488722606098801
585 1000597050163575897237
586 1047394164882567583279
587 1096338387743584482935
588 1147526364208369879531
589 1201059007715731651666
590 1257041684607853259761
591 1315584406918672101555
592 1376802033352319072553
593 1440814478793042224932
594 1507746932701999978014
595 1577730086770841624185
596 1650900372217105274107
597 1727400207122175217193
598 1807378254228891659118
599 1890989689632908209110
600 1978396482819568484631
601 2069767688516465860887
602 2165279750850974608378
603 2265116820321921337266
604 2369471084115250018176
605 2478543110315039290835
606 2592542206583585766103
607 2711686793907522835245
608 2836204796031121959760
609 2966334045223054402208
610 3102322705049032170033
611 3244429710849921736679
612 3392925228653169097264
613 3548091133274751286266
614 3710221506399406020344
615 3879623155458628228455
616 4056616154158927400000
617 4241534405547145524220
618 4434726228535288007650
619 4636554968844393015603
620 4847399635365496162468
621 5067655562975789035562
622 5297735102889702732268
623 5538068341667914908273
624 5789103850052239192783
625 6051309462841097904325
626 6325173091068853070935
627 6611203567802742174388
628 6909931528923631573744
629 7221910330311319451156
630 7547717002911765133620
631 7887953247222499991319
632 8243246468793652448847
633 8614250856405578581705
634 9001648504650148537258
635 9406150582711372139067
636 9828498551212347622583
637 10269465429069615267444
638 10729857112372977938564
639 11210513747388817333057
640 11712311159868031318687
641 12236162342926040614073
642 12783019005851979242361
643 13353873186297350306259
644 13949758928391206398566
645 14571754029429433231617
646 15220981857890150032719
647 15898613245635714736157
648 16605868457274483045049
649 17344019239772509811372
650 18114390955526939307667
651 18918364802239072168987
652 19757380123056233060943
653 20632936810587752770228
654 21546597808541805713630
655 22499991714876742541031
656 23494815490513106583448
657 24532837277810928137269
658 25615899333181410635176
659 26745921078372958958037
660 27924902275148883045746
661 29154926328258325062782
662 30438163721793232692166
663 31776875594222792109986
664 33173417457602957830850
665 34630243066672827882336
666 36149908443771899867253
667 37735076065743055373925
668 39388519219225743987491
669 41113126530992595365643
670 42911906680240964942919
671 44787993300019037857757
672 46744650075244436130986
673 48785276045062223248677
674 50913411117589139926860
675 53132741805402235877106
676 55447107190453258275055
677 57860505127425623579542
678 60377098694898983403715
679 63001222904047820885087
680 65737391674975636072688
681 68590305091175596755222
682 71564856943012625046447
683 74666142571541268740291
684 77899467024408927578296
685 81270353536045710160148
686 84784552344810957383870
687 88448049860252904300275
688 92267078194142775833349
689 96248125069468460219373
690 100397944122116470402950
691 104723565610534975983138
692 109232307549255979659460
693 113931787282761994592709
694 118829933516812726189066
695 123934998825001069917876
696 129255572648986066794212
697 134800594811554277377935
698 140579369562391233846811
699 146601580177202166305922
700 152877304131607146445124
701 159417028872051142553566
702 166231668206815302570490
703 173332579341093264347294
704 180731580581006544123331
705 188440969732377263707622
706 196473543221055961371985
707 204842615962618228149063
708 213562042010297743552749
709 222646236011116412123426
710 232110195501306104970064
711 241969524073292460909409
712 252240455447730917992286
713 262939878485350166457706
714 274085363174670177059920
715 285695187633022657163495
716 297788366159712935980302
717 310384678381625701763011
718 323504699533094695681942
719 337169831913430319301153
720 351402337567131161854015
721 366225372233497902813746
722 381663020614123021975025
723 397740333008549506353904
724 414483363370278722967762
725 431919208837264196725623
726 450076050793056698365066
727 468983197516869514770647
728 488671128483013679073063
729 509171540372414063992888
730 530517394861261588975532
731 552742968254287291915198
732 575883903032663762936212
733 599977261389151755060457
734 625061580825817936669852
735 651176931892457169025786
736 678364978146763063617874
737 706669038420307525167221
738 736134151477517333365322
739 766807143158077642538851
740 798736696096552615460982
741 831973422116496492999528
742 866569937399938759847543
743 902580940536869178665121
744 940063293563227035890424
745 979076106099918984908256
746 1019680822709556365176144
747 1061941313591921041313417
748 1105923968743644198786053
749 1151697795712220682362906
750 1199334521079288166195269
751 1248908695813081853291896
752 1300497804635137658862209
753 1354182379551666367176563
754 1410046117705564882231222
755 1468176003710775236412272
756 1528662436636654613524373
757 1591599361816187832967280
758 1657084407658265099235113
759 1725219027650870258215799
760 1796108647748886682017544
761 1869862819347337625714518
762 1946595378048244238423427
763 2026424608436916628477068
764 2109473415091400796987264
765 2195869500056996595280108
766 2285745547026249385741492
767 2379239412473611128298152
768 2476494324003075962927337
769 2577659086176532367243014
770 2682888294100350100732685
771 2792342555057847358488618
772 2906188718485774419469497
773 3024600114603817296888448
774 3147756802017381730146104
775 3275845824625578215199843
776 3409061478178406743448556
777 3547605586839650186334096
778 3691687790124943228836779
779 3841525840597905034960444
780 3997345912721124683461860
781 4159382923273185890901454
782 4327880863757828945455257
783 4503093145246791118791941
784 4685282956113860971761949
785 4874723633134246092153436
786 5071699046440507844770747
787 5276503998844081550513247
788 5489444640049797376585748
789 5710838896309868197049275
790 5941016916083538867854346
791 6180321532289020268528367
792 6429108741755485540822468
793 6687748202504810751397453
794 6956623749515423759178091
795 7236133929644110436158559
796 7526692556405944833285359
797 7828729285337688224412355
798 8142690210696071146419599
799 8469038484269363835172485
800 8808254957108585739552534
801 9160838845013637211921476
802 9527308418639590583579494
803 9908201719119388943663400
804 10304077300131305705191271
805 10715514997372754673597542
806 11143116726436447896066799
807 11587507310120517608346875
808 12049335336241091354086375
809 12529274047053979044089129
810 13028022261431642189937966
811 13546305330982515483247416
812 14084876131342087096468677
813 14644516089908966135929281
814 15226036251344525192787704
815 15830278382201655769664375
816 16458116116096769329067712
817 17110456140889473846543585
818 17788239429386413500943745
819 18492442515139638092852301
820 19224078814965631968789802
821 19984199999868844251548125
822 20773897416113290011108977
823 21594303558247605277785049
824 22446593595952908912730461
825 23331986956649025321868773
826 24251748965863130736839222
827 25207192547435781209632584
828 26199679985712644352987359
829 27230624751946174151181032
830 28301493397210026068181418
831 29413807514210298532415826
832 30569145770461800490300302
833 31769146015384579431406951
834 33015507463965999884855482
835 34309992959726842454019803
836 35654431319826304409953463
837 37050719765240534907058305
838 38500826439052545383151829
839 40006793015998116184876881
840 41570737406522795610829691
841 43194856558719383636957311
842 44881429361633539358825305
843 46632819653547483008573976
844 48451479338978319630287109
845 50339951618258435407506519
846 52300874333700857547884383
847 54336983436492578328616759
848 56451116578603781562789710
849 58646216834150839062719816
850 60925336554806035351391825
851 63291641364007405483206639
852 65748414294888014039468729
853 68299060077015650393443333
854 70947109577211458851754395
855 73696224399899661613700974
856 76550201652630474197370794
857 79512978882614769636617950
858 82588639190312239281686450
859 85781416526324952265025100
860 89095701178065567144542651
861 92536045452894240506651157
862 96107169564650759666362360
863 99813967730748858733343243
864 103661514487248326792942275
865 107655071229577660854515891
866 111800092986845939860714852
867 116102235437957594501243328
868 120567362178028126331717773
869 125201552243892903389421847
870 130011107907805253476667897
871 135002562748734527338232712
872 140182690010999958995862407
873 145558511260312368210118995
874 151137305347643401656653147
875 156926617691701477363233369
876 162934269891165276646149609
877 169168369678209928363024053
878 175637321225258373308597809
879 182349835817301217801007762
880 189314942902553135822967021
881 196542001534653023081109526
882 204040712220069124260982268
883 211821129184839743386841812
884 219893673075265418497795605
885 228269144107670124968270404
886 236958735682867714059192661
887 245974048481505958752010940
888 255327105057014850550117408
889 265030364943458771638538466
890 275096740296184477973308416
891 285539612083769112681879664
892 296372846850405389643063985
893 307610814068515328742408537
894 319268404102060194336491123
895 331361046801713318195119412
896 343904730753785031450074046
897 356916023205535765738855551
898 370412090690285317028125837
899 384410720376524126632705658
900 398930342166057080333458174
901 413990051567062644782081185
902 429609633368831064530956102
903 445809586145855777237374801
904 462611147619893144796360144
905 480036320909578050524460613
906 498107901698187916423592414
907 516849506351186324191732757
908 536285601016250786544265942
909 556441531739598455556589051
910 577343555633569854333527975
911 599018873131615296281484494
912 621495661368052771578974030
913 644803108721231034000443956
914 668971450560038754403832595
915 694032006235051305269938318
916 720017217357002435001126332
917 746960687406710257128541860
918 774897222722077142304933641
919 803862874909322834592049786
920 833894984727201041773771429
921 865032227494593548929483086
922 897314660073574307332839139
923 930783769481790742952526329
924 965482523189822554670142823
925 1001455421161051436761245225
926 1038748549693510427614273211
927 1077409637125180985364429700
928 1117488111466271515984080605
929 1159035160024145090675546241
930 1202103791088768717544302810
931 1246748897748834080938253839
932 1293027323911052505900445766
933 1340997932597557497216342181
934 1390721676598859074999132699
935 1442261671562387893200673329
936 1495683271599346479853255431
937 1551054147495352662114518425
938 1608444367613219206152064746
939 1667926481579166875057989080
940 1729575606846818547206487583
941 1793469518236472898235136725
942 1859688740550410689270336866
943 1928316644368348284950426566
944 1999439545130625115112581550
945 2073146805620297973100746405
946 2149530941959019006822115099
947 2228687733235399816666346296
948 2310716334888515160274023578
949 2395719395973280438039269841
950 2483803180438651582119215162
951 2575077692553948516735215791
952 2669656806623098459144368924
953 2767658401131237588582939769
954 2869204497472903771640598667
955 2974421403416003996548374402
956 3083439861460852988357733716
957 3196395202258859365923383821
958 3313427503260888041375306040
959 3434681752770957902720354810
960 3560308019586747886642544513
961 3690461628414388251274172876
962 3825303341251213291860835325
963 3964999544936553194013774666
964 4109722445077252678937444809
965 4259650266561429254298839087
966 4414967460881031147613300931
967 4575864920491031490919236983
968 4742540200440608392933568976
969 4915197747519417757782489894
970 5094049137170074909292870689
971 5279313318426230321863912494
972 5471216867144162363802162265
973 5669994247804624512038090657
974 5875888084170784850990601727
975 6089149439097490955686566296
976 6310038103796792902728270300
977 6538822896874670868163167688
978 6775781973464251581461447989
979 7021203144791470150024258026
980 7275384208520151110838022615
981 7538633290234856003214293637
982 7811269196431585635149775531
983 8093621779398545234404233901
984 8386032314381691901020999129
985 8688853889442698658947906713
986 9002451808430300775432671101
987 9327204007499751116307178037
988 9663501485629315788932032577
989 10011748749597403271940779872
990 10372364273899054163558677504
991 10745780976096139576878949932
992 11132446708111739514163110601
993 11532824763995814190254066704
994 11947394404706457675408458608
995 12376651400468751327034368229
996 12821108591291531744959909472
997 13281296466241272431050218074
998 13757763762091768533958173555
999 14251078081988429166863701041
1000 14761826534786741553622857599