0 1
1 1
2 1
3 2
4 3
5 4
6 6
7 8
8 12
9 16
10 22
11 29
12 40
13 52
14 69
15 90
16 118
17 151
18 195
19 248
20 317
21 400
22 505
23 632
24 793
25 985
26 1224
27 1512
28 1867
29 2291
30 2811
31 3431
32 4186
33 5084
34 6168
35 7456
36 9005
37 10836
38 13026
39 15613
40 18692
41 22316
42 26613
43 31659
44 37619
45 44601
46 52815
47 62416
48 73680
49 86809
50 102162
51 120025
52 140853
53 165028
54 193144
55 225710
56 263490
57 307161
58 357699
59 416006
60 483338
61 560864
62 650196
63 752877
64 870953
65 1006426
66 1161916
67 1340012
68 1544048
69 1777365
70 2044188
71 2348821
72 2696627
73 3093095
74 3545015
75 4059416
76 4644850
77 5310255
78 6066425
79 6924691
80 7898630
81 9002580
82 10253568
83 11669704
84 13272332
85 15084211
86 17132044
87 19444436
88 22054694
89 24998640
90 28317803
91 32056941
92 36267714
93 41005947
94 46335767
95 52326672
96 59058176
97 66616548
98 75100211
99 84616150
100 95285933
101 107241923
102 120634125
103 135625995
104 152402294
105 171164557
106 192139963
107 215576593
108 241753433
109 270975242
110 303584109
111 339953965
112 380503578
113 425690950
114 476028109
115 532075157
116 594457221
117 663858302
118 741040507
119 826837956
120 922178606
121 1028078054
122 1145664693
123 1276173587
124 1420974960
125 1581568632
126 1759616557
127 1956937635
128 2175545082
129 2417642016
130 2685664089
131 2982276475
132 3310422523
133 3673322195
134 4074528159
135 4517926253
136 5007799482
137 5548831584
138 6146180442
139 6805484958
140 7532949590
141 8335355650
142 9220158247
143 10195503546
144 11270340005
145 12454442414
146 13758540358
147 15194350744
148 16774725237
149 18513693839
150 20426634675
151 22530330140
152 24843162935
153 27385187785
154 30178357193
155 33246612592
156 36616144467
157 40315506042
158 44375914168
159 48831390225
160 53719106921
161 59079562675
162 64956982102
163 71399529150
164 78459770304
165 86194934299
166 94667447031
167 103945247454
168 114102405525
169 125219503502
170 137384351371
171 150692445800
172 165247796646
173 181163478912
174 198562588546
175 217578902413
176 238357984581
177 261057974047
178 285850863883
179 312923440362
180 342478762147
181 374737275534
182 409938526880
183 448342484721
184 490231519559
185 535911970005
186 585716432648
187 640005611405
188 699170967038
189 763636898176
190 833863804673
191 910350657428
192 993638539962
193 1084313669342
194 1183011492536
195 1290420233355
196 1407285626147
197 1534415077278
198 1672683135737
199 1823036366105
200 1986499671158
201 2164181992422
202 2357283613018
203 2567102821165
204 2795044343438
205 3042627122079
206 3311494054514
207 3603421062158
208 3920328330754
209 4264290877936
210 4637551523826
211 5042533188856
212 5481853858834
213 5958340884921
214 6475048240693
215 7035273138840
216 7642575925363
217 8300799367402
218 9014091584553
219 9786928420126
220 10624139858112
221 11530935954694
222 12512937262692
223 13576204860949
224 14727275385145
225 15973195779023
226 17321563609480
227 18780567257515
228 20359032298640
229 22066467946444
230 23913120397333
231 25910026464628
232 28069074902464
233 30403068308605
234 32925793597839
235 35652093394379
236 38597946993835
237 41780552651027
238 45218420549441
239 48931467594861
240 52941124133557
241 57270443078809
242 61944222372090
243 66989130538333
244 72433847147773
245 78309207198319
246 84648362166157
247 91486945934852
248 98863259387551
249 106818460997215
250 115396778310845
251 124645726756016
252 134616351842882
253 145363480221008
254 156945996964271
255 169427133485129
256 182874784847878
257 197361839793595
258 212966543725896
259 229772876802972
260 247870969018586
261 267357533153993
262 288336339236933
263 310918710084228
264 335224063427995
265 361380478813866
266 389525316822980
267 419805867301272
268 452380056354758
269 487417187250223
270 525098747327607
271 565619254418607
272 609187177461859
273 656025903041194
274 706374785316398
275 760490249255397
276 818646987602104
277 881139219569289
278 948282054947232
279 1020412929553802
280 1097893159226402
281 1181109576176798
282 1270476298657758
283 1366436595540219
284 1469464900867384
285 1580068937617744
286 1698792010182008
287 1826215422374719
288 1962961085239727
289 2109694268949485
290 2267126568272699
291 2436019033230519
292 2617185540049481
293 2811496351331932
294 3019881946594520
295 3243337069283114
296 3482925078045049
297 3739782545412617
298 4015124198846010
299 4310248144331735
300 4626541475193425
301 4965486203273301
302 5328665623593822
303 5717771046486883
304 6134609017455669
305 6581108955643450
306 7059331341037265
307 7571476378118214
308 8119893276906634
309 8707090075877362
310 9335744159426003
311 10008713391247362
312 10729048028979543
313 11500003338401991
314 12325053086440349
315 13207903828187452
316 14152510182294055
317 15163091007121797
318 16244146688351003
319 17400477447769442
320 18637202901868647
321 19959782777454351
322 21374039032406253
323 22886179286708273
324 24502821833044635
325 26231022130362475
326 28078301072924502
327 30052674936877675
328 32162687322176868
329 34417442991249831
330 36826643949750324
331 39400627670790814
332 42150407838222896
333 45087717511058478
334 48225055117579740
335 51575733183063381
336 55153930235582573
337 58974745796756772
338 63054258941385679
339 67409590336951526
340 72058968290076968
341 77021798716793472
342 82318739610778598
343 87971779934030813
344 94004323555916610
345 100441278174591857
346 107309149903404234
347 114636143468412820
348 122452268761571633
349 130789453710561880
350 139681664277984816
351 149165031568693103
352 159277986932696068
353 170061405064075112
354 181558756065135164
355 193816266501929437
356 206883090510462438
357 220811491009889043
358 235657032180871515
359 251478783301180396
360 268339535205081174
361 286306029500356999
362 305449201928932058
363 325844440053296911
364 347571856785922603
365 370716580000299865
366 395369059884829412
367 421625394343310622
368 449587674262072455
369 479364349022239074
370 511070614251846573
371 544828822282542624
372 580768917497559464
373 619028897134443136
374 659755299940989585
375 703103723360440008
376 749239371877508188
377 798337637330191203
378 850584714075392933
379 906178249959977690
380 965328036268312714
381 1028256737764320020
382 1095200666310896652
383 1166410599374062737
384 1242152647238021780
385 1322709170452985614
386 1408379751720964486
387 1499482223983711007
388 1596353759335847973
389 1699352020801864770
390 1808856382060400000
391 1925269217464240208
392 2049017267947868198
393 2180553085519877265
394 2320356562492834580
395 2468936548541534560
396 2626832562360473550
397 2794616601454368874
398 2972895057515422479
399 3162310741418594367
400 3363545026042077021
401 3577320111503785370
402 3804401421852166241
403 4045600138430032111
404 4301775879867863696
405 4573839534628998805
406 4862756257076527102
407 5169548633773745196
408 5495300032106173820
409 5841158138820994573
410 6208338701807248878
411 6598129483701389567
412 7011894442005318190
413 7451078145408300311
414 7917210442505066203
415 8411911393838459790
416 8936896485121878317
417 9493982133951103748
418 10085091509696809621
419 10712260680430481316
420 11377645108601751229
421 12083526511041755885
422 12832320107249534630
423 13626582273455769130
424 14469018628893122822
425 15362492573908704705
426 16310034309077049584
427 17314850357334785351
428 18380333621310142021
429 19510074000524712510
430 20707869603969299373
431 21977738585689560888
432 23323931642557872414
433 24750945205158909903
434 26263535365023922270
435 27866732572801796923
436 29565857155082708059
437 31366535688534084953
438 33274718284010754229
439 35296696823824161172
440 37439124210294462544
441 39709034673797093666
442 42113865204456975962
443 44661478161286358382
444 47360185129574068554
445 50218772086522051179
446 53246525953283993791
447 56453262600281822770
448 59849356392063753043
449 63445771346214791750
450 67254094001531547368
451 71286568078440378940
452 75556131036747528158
453 80076452623088539474
454 84861975524064146283
455 89927958227838358047
456 95290520222209958626
457 100966689643466790885
458 106974453517302139022
459 113332810718878162162
460 120061827807952715146
461 127182697880305609612
462 134717802607525180052
463 142690777622058656546
464 151126581437396789518
465 160051568077636769428
466 169493563625935362520
467 179481946885287503033
468 190047734382800700866
469 201223669932131414435
470 213044319009138123695
471 225546168178897201877
472 238767729855469463867
473 252749652658529016458
474 267534837677270699150
475 283168560934411337881
476 299698602392702065088
477 317175381828488409051
478 335652101950005742254
479 355184899120000125304
480 375833002099229990597
481 397658899209161246875
482 420728514373243975552
483 445111392477847571669
484 470880894559435143053
485 498114403306277186755
486 526893539433273801654
487 557304389470316520926
488 589437745580029870619
489 623389358002858694117
490 659260200808419233431
491 697156751614571573050
492 737191286022594894908
493 779482187499968819328
494 824154273535634925170
495 871339138876499829930
496 921175516754271807594
497 973809658996595347843
498 1029395736024285204387
499 1088096257722564963285
500 1150082516290163799799
501 1215535052157728174181
502 1284644144191718558434
503 1357610325389379232553
504 1434644925404546382844
505 1515970641235644460006
506 1601822137551633199728
507 1692446678125803856421
508 1788104790002805589794
509 1889070962021415977430
510 1995634379483016900855
511 2108099696756362286402
512 2226787849789622936153
513 2352036910505353502960
514 2484202985248444831948
515 2623661159466440213046
516 2770806491011180056199
517 2926055054465399389878
518 3089845039123919717994
519 3262637903279835837368
520 3444919587709916221864
521 3637201791281150838642
522 3840023311863474065033
523 4053951455769310437411
524 4279583519224582038058
525 4517548345420380827490
526 4768507961001156087483
527 5033159295899948453464
528 5312235990762402450202
529 5606510296267383347695
530 5916795069009861276440
531 6243945868690651790984
532 6588863161744337670359
533 6952494636630048267349
534 7335837636427850335216
535 7739941714493038387800
536 8165911319372712870612
537 8614908615316677008037
538 9088156445203717277719
539 9586941442852234247688
540 10112617302213308750235
541 10666608211114819309586
542 11250412457797880958042
543 11865606218682631897742
544 12513847536420336603628
545 13196880497512645108082
546 13916539619450141464868
547 14674754457577479835276
548 15473554442619500963615
549 16315073960092664254845
550 17201557683613863732939
551 18135366174447279278050
552 19118981760483531377479
553 20155014708216878863814
554 21246209702211438780503
555 22395452646966417293408
556 23605777807093445619130
557 24880375302190809844943
558 26222598973887105919342
559 27635974643056882602957
560 29124208776390621623628
561 30691197582095958536940
562 32341036555786935507880
563 34078030498283984754324
564 35906704028436077766792
565 37831812614821230761958
566 39858354151688702312815
567 41991581105338021975229
568 44237013258765947055483
569 46600451083340332673813
570 49087989768035970459056
571 51706033937801331528663
572 54461313094553676030909
573 57360897815450699974699
574 60412216745181306738905
575 63623074420297550086219
576 67001669965884699310367
577 70556616706287648422219
578 74296962734083220855934
579 78232212483065282718656
580 82372349353694680895683
581 86727859441215163471299
582 91309756419554171287541
583 96129607636065483970326
584 101199561475341643228147
585 106532376052469891973529
586 112141449299551913998549
587 118040850511681791603207
588 124245353422323102459442
589 130770470880651056890508
590 137632491207498605195777
591 144848516309445882213488
592 152436501635020825625668
593 160415298060181677999076
594 168804695795067432247305
595 177625470407537082721000
596 186899431064255063468716
597 196649471093979190555417
598 206899620983402432054636
599 217675103920198163575855
600 229002394004112641422060
601 240909277251684690681991
602 253424915526909986992101
603 266579913535383561990795
604 280406389026782996789370
605 294938046356297019367088
606 310210253563576863207225
607 326260123134106243067899
608 343126596616559310183698
609 360850533276665514506814
610 379474802977536759513486
611 399044383484052797909293
612 419606462399167741896125
613 441210543948397532330378
614 463908560839919157659690
615 487754991436937125672474
616 512806982491127687484617
617 539124477696101694898536
618 566770352333053038710240
619 595810554291880676373224
620 626314251765464167719020
621 658353987926977049814515
622 692005842915783234179756
623 727349603470850543161147
624 764468940567657395389920
625 803451595429252417205137
626 844389574300671735697147
627 887379352392017517121852
628 932522087415682123612558
629 979923843160847259593572
630 1029695823570348434254076
631 1081954617804329189733130
632 1136822456799007718103980
633 1194427481850057437014188
634 1254904025776109294534801
635 1318392907241077114455255
636 1385041738842307197121179
637 1455005249596946472606064
638 1528445622489719133173131
639 1605532847773095680763453
640 1686445092744349331822447
641 1771369088754409127460813
642 1860500536239884207697111
643 1954044528602907498298713
644 2052215995803125943857004
645 2155240168562557730441651
646 2263353064127211864363357
647 2376801994569161652466564
648 2495846098659741321326280
649 2620756898388042485020315
650 2751818881250001166043894
651 2889330109480920434384965
652 3033602857459886506486874
653 3184964278566502763090003
654 3343757102830871524259550
655 3510340366774529838099362
656 3685090176905871633166713
657 3868400508395607218602712
658 4060684040529423076995422
659 4262373030602736307736896
660 4473920228000341183337648
661 4695799830277701282536615
662 4928508483145384018014122
663 5172566326338871474810223
664 5428518087448161559460270
665 5696934225869697000052873
666 5978412129143424340968514
667 6273577364033953219381164
668 6583084984823839115211684
669 6907620901391940912521508
670 7247903309768410128524797
671 7604684187972334672794279
672 7978750860067048011738118
673 8370927631492963904374015
674 8782077498878068728666674
675 9213103937662354632430077
676 9664952771025011072162154
677 10138614123751643890160599
678 10635124464844650227919791
679 11155568742841714328727107
680 11701082617987726751179861
681 12272854795581829794207424
682 12872129465017359820737523
683 13500208849224701210035109
684 14158455869440223854838623
685 14848296930433954412736035
686 15571224831560353072175148
687 16328801809224790058723204
688 17122662716610202770684430
689 17954518346757020946699951
690 18826158905363235890535456
691 19739457639942260837191170
692 20696374632273804949600723
693 21698960761377851861459991
694 22749361844565240763100791
695 23849822964439412250062786
696 25002692990075338134851417
697 26210429300951192075148206
698 27475602722590231288103585
699 28800902683250842418103620
700 30189142601417684731488934
701 31643265514260974333147280
702 33166349957681830697699368
703 34761616109012255792042594
704 36432432203928161434252765
705 38182321239624205783290791
706 40014967976831342315928905
707 41934226253791452214502866
708 43944126625881480384576641
709 46048884345159801497494410
710 48252907694735412614261639
711 50560806693491724240760864
712 52977402187378655876266430
713 55507735344173158008302025
714 58157077569348880184716035
715 60930940861442101638121653
716 63835088626105287871182367
717 66875546968851154044155253
718 70058616487363415869174153
719 73390884585132619407087525
720 76879238329123649828325196
721 80530877875140464242617081
722 84353330485583057247581364
723 88354465165333895253696995
724 92542507942628650285487375
725 96926057822898671250970506
726 101514103444785806172249364
727 106316040468760867890912596
728 111341689730093863366098415
729 116601316189261192310920700
730 122105648714304243872406422
731 127865900731106343903253140
732 133893791779106093840221120
733 140201570011542889312188673
734 146802035681013618027702134
735 153708565652833106920034910
736 160935138990517331568125184
737 168496363659569277404011926
738 176407504397729046043963225
739 184684511801870419745076307
740 193344052683876087406609383
741 202403541750017567604570186
742 211881174660698244285002851
743 221795962529799561823547050
744 232167767925400463978623369
745 243017342436225385867782360
746 254366365870920332210995850
747 266237487160062493722933573
748 278654367033785155060883832
749 291641722550944774278755090
750 305225373558984856627883532
751 319432291166955621416988846
752 334290648317648602295035100
753 349829872548390639201836915
754 366080701033836939885200362
755 383075238007992627776702417
756 400847014666807030815793712
757 419431051656904535008045175
758 438863924260476835147107495
759 459183830390938310034760808
760 480430661518782156082120474
761 502646076652038885173349227
762 525873579500980673593128708
763 550158598962098286585268812
764 575548573062058774946695315
765 602093036508189465718719048
766 629843711998191192053457011
767 658854605448112789933009883
768 689182105304291587850916285
769 720885086111826199264530602
770 754025016519378429199298807
771 788666071907539257156720745
772 824875251835828150559848572
773 862722502511457336756637273
774 902280844491480468070667043
775 943626505838683244008132200
776 986839060960768636722663676
777 1032001575371858971057649812
778 1079200756625297588298097966
779 1128527111676994146896423866
780 1180075110949346314349036261
781 1233943359376888774794645286
782 1290234774726505312526981133
783 1349056773497085149040393990
784 1410521464716159081774352765
785 1474745851964099733658903061
786 1541852043970173453436452342
787 1611967474138865755916722862
788 1685225129379740006333078048
789 1761763788629397872053656235
790 1841728271470175093550901678
791 1925269697266785463516503426
792 2012545755259518228141673094
793 2103720986070547761528308056
794 2198967075098742115027024911
795 2298463158297797109106489154
796 2402396140852902623596015776
797 2510961029292195375886771676
798 2624361277591310882945003037
799 2742809147852133365579270728
800 2866526086160715470013815443
801 2995743114254005523873182447
802 3130701237650855071664777562
803 3271651870929477727256898460
804 3418857280861486289773900595
805 3572591048141530694746914090
806 3733138548481807829995892944
807 3900797453871985260052458844
808 4075878254837807273266812205
809 4258704804565490337503808388
810 4449614885794419469747312194
811 4648960801417270951112899149
812 4857109989764985358973117928
813 5074445665593628197149672976
814 5301367487831601321852134369
815 5538292255188523013383705493
816 5785654630771899622802895396
817 6043907896904068905377662354
818 6313524741380351164097627660
819 6594998076459485958378893765
820 6888841891929832391860316624
821 7195592143649041349226451797
822 7515807679011569101050494171
823 7850071200857049151561981277
824 8198990271393802630593988840
825 8563198357775186443280519481
826 8943355921032712776619156829
827 9340151550138446296778694695
828 9754303143040788394452738936
829 10186559136591896947738953736
830 10637699787362390776217508431
831 11108538505419138541106703326
832 11599923243225593074452780349
833 12112737941910774330966523058
834 12647904037243425175127861150
835 13206382027741516006002444773
836 13789173107444993552322273236
837 14397320865980889208205146211
838 15031913058655500734015889910
839 15694083449417751979187285200
840 16385013729651939240724244697
841 17105935515876284315740117365
842 17858132429546999238445359375
843 18642942262295300491873644125
844 19461759230058004748334308578
845 20316036319700347953181321854
846 21207287731873558482749646063
847 22137091423998816527291292573
848 23107091757424662100244796436
849 24119002252965985500055581660
850 25174608459200618401452763879
851 26275770938073532080602199025
852 27424428372539971663292324109
853 28622600801166781235900298970
854 29872392984806995654537091955
855 31175997910665738676215333083
856 32535700439286929744909334565
857 33953881100209489208178765965
858 35433020042270068119896896829
859 36975701144766017861780518855
860 38584616295938852494163372545
861 40262569845494024660947295511
862 42012483238139005467144866240
863 43837399835397589524492169699
864 45740489933245689354150527819
865 47725055983411775986894981246
866 49794538026495299821936047168
867 51952519345378003110827261245
868 54202732347737836157047017113
869 56549064686822307278421356410
870 58995565629999448325572709618
871 61546452684979235524105543392
872 64206118493988284474126146542
873 66979138006584989785657480428
874 69870275942223122610805381950
875 72884494554108264331119307928
876 76026961706345569822895451102
877 79303059276848230400183285964
878 82718391898965988107156456790
879 86278796055301131921625891170
880 89990349537708047857688148928
881 93859381288020573385341309156
882 97892481634621715848573305388
883 102096512940561692318764350730
884 106478620679545464194977876455
885 111046244956748916027527818266
886 115807132492086437547676665869
887 120769349084240838947935232064
888 125941292574482286624772813101
889 131331706330045205888407419457
890 136949693267604043179356910779
891 142804730438189318931860098564
892 148906684195717887170509387765
893 155265825972174647112602889961
894 161892848683380658059234057207
895 168798883790213584227554656159
896 175995519041114362526839829375
897 183494816922717833662350417491
898 191309333846488726895496171840
899 199452140100326732087685874827
900 207936840595229562279881058485
901 216777596438269801155552535674
902 225989147364354298957694872307
903 235586835060492831290374086887
904 245586627417610261089658029208
905 256005143746292461230858854104
906 266859680994265607620020193065
907 278168241004870074309855533803
908 289949558857309162246456993425
909 302223132331028229051470028105
910 315009252538216848638302517415
911 328329035770124403095575862384
912 342204456604643682384189877429
913 356658382324446662590285111339
914 371714608696857652988891600855
915 387397897168620511892076337672
916 403734013530764967159031552388
917 420749768110901356565795734354
918 438473057552480015610102965806
919 456932908242840263192740301117
920 476159521454251533462432426004
921 496184320264614922255701369227
922 517039998327054720900584219586
923 538760570560285726505201457873
924 561381425834401129489013161799
925 584939381729587005984478601759
926 609472741448241214997976114574
927 635021352964056342627117622190
928 661626670494827052398692702894
929 689331818389061435327715706812
930 718181657519923012761265442908
931 748222854283604706643641918883
932 779503952302948196386269298183
933 812075446940971556454220205991
934 845989862732965321427628248423
935 881301833849962251212020351556
936 918068187710690076930977653551
937 956348031863579681046869065489
938 996202844265035150566870126333
939 1037696567084977431863133956145
940 1080895704175662234853814841147
941 1125869422344946107001489685584
942 1172689656580545269136502674649
943 1221431219377400856365008062125
944 1272171914326045448667043464185
945 1324992654125860472140359971668
946 1379977583193336826471989468977
947 1437214205041903525522823045089
948 1496793514616586712987273204798
949 1558810135773706057762595635280
950 1623362464103023649150541482503
951 1690552815297234404129805536148
952 1760487579281444048915811333706
953 1833277380323323666107694871693
954 1909037243352977025838574906136
955 1987886766730211623716388821460
956 2069950301705886052345025560876
957 2155357138833318717890981357707
958 2244241701595406674459393613695
959 2336743747523122717244801858771
960 2433008577091455794788118303497
961 2533187250689639102003003938112
962 2637436813973695171205237006607
963 2745920531920923374894539658203
964 2858808131917987176799897311155
965 2976276056226732419151647081191
966 3098507724184810103249167542497
967 3225693804511594489967048435217
968 3358032498103807706186063600241
969 3495729831719693225164232556755
970 3638999962965552086362585105782
971 3788065497013976291477983073933
972 3943157815499214764673698553202
973 4104517418051798361058842767460
974 4272394276951864885438661244485
975 4447048205398573802143251956433
976 4628749239911618569482580219136
977 4817778037400144366426924010692
978 5014426287454397877236643030117
979 5218997140436187099507955835990
980 5431805651965752657376900765435
981 5653179244424962571740792903632
982 5883458186119882162502615181553
983 6122996088769755989132217215853
984 6372160424014314421021211195893
985 6631333059657101468251150927444
986 6900910816389260662019836092638
987 7181306045765931733941703701194
988 7472947230236153374935071702254
989 7776279606056958068397836065164
990 8091765809953237860975338140221
991 8419886550416978656059338614377
992 8761141304572662574868392156419
993 9116049041570049084353194338913
994 9485148973501226962218065783480
995 9869001334875809155483171895491
996 10268188191726486089453089419757
997 10683314281456891036071681173407
998 11115007884584932787021029432044
999 11563921729577449985956018909705
1000 12030733932016311495363956097651