0 1
1 1
2 1
3 3
4 3
5 7
6 8
7 14
8 16
9 26
10 32
11 45
12 57
13 78
14 103
15 132
16 174
17 220
18 295
19 361
20 477
21 584
22 766
23 921
24 1194
25 1436
26 1841
27 2207
28 2782
29 3331
30 4169
31 4981
32 6156
33 7373
34 9019
35 10778
36 13093
37 15636
38 18843
39 22507
40 26920
41 32096
42 38205
43 45470
44 53845
45 63970
46 75377
47 89356
48 104936
49 124062
50 145169
51 171251
52 199783
53 234958
54 273381
55 320728
56 372300
57 435546
58 504448
59 588613
60 680521
61 791836
62 913745
63 1060678
64 1222030
65 1414893
66 1627471
67 1879986
68 2159460
69 2488594
70 2854340
71 3282483
72 3759916
73 4314696
74 4935529
75 5652839
76 6458006
77 7382230
78 8422743
79 9611334
80 10952481
81 12476353
82 14199284
83 16149147
84 18356872
85 20845083
86 23665430
87 26834135
88 30428619
89 34454208
90 39022492
91 44126377
92 49918581
93 56375257
94 63700833
95 71853118
96 81097330
97 91368423
98 103007113
99 115923490
100 130546037
101 146756735
102 165088931
103 185396452
104 208333263
105 233726699
106 262368312
107 294062605
108 329762226
109 369251112
110 413664651
111 462780452
112 517937452
113 578922734
114 647305683
115 722900550
116 807536234
117 901091798
118 1005675114
119 1121268190
120 1250296076
121 1392895085
122 1551835782
123 1727478802
124 1922970420
125 2138989336
126 2379091844
127 2644366171
128 2938829100
129 3264131272
130 3624763982
131 4023093764
132 4464159816
133 4951241226
134 5489959585
135 6084746271
136 6741869502
137 7467211763
138 8267753064
139 9151127956
140 10125141167
141 11199624193
142 12383256819
143 13688510424
144 15125128006
145 16708778249
146 18450393514
147 20369473310
148 22478361589
149 24801172107
150 27351900496
151 30160064779
152 33241702291
153 36632805385
154 40351779093
155 44442189643
156 48925423598
157 53853968547
158 59252783858
159 65184752916
160 71679283138
161 78811451290
162 86616075723
163 95182297855
164 104551723941
165 114829922324
166 126066719718
167 138386596941
168 151849662086
169 166602307028
170 182717168107
171 200365829213
172 219636400105
173 240729567979
174 263752307069
175 288938606835
176 316418643080
177 346464808739
178 379235378514
179 415046670088
180 454091272201
181 496736022323
182 543214921346
183 593952561363
184 649233158100
185 709547642159
186 775240533751
187 846878666209
188 924879136615
189 1009895952150
190 1102432966373
191 1203243981779
192 1312936650108
193 1432379398184
194 1562303373695
195 1703708401159
196 1857472526682
197 2024746660093
198 2206582727323
199 2404305217971
200 2619171791171
201 2852706668309
202 3106410144258
203 3382036290301
204 3681370960015
205 4006433288663
206 4359344491413
207 4742429185805
208 5158201798547
209 5609339652015
210 6098817136057
211 6629719071167
212 7205556879337
213 7829886447272
214 8506845470463
215 9240534846854
216 10035820923469
217 10897435567057
218 11831092047429
219 12842253251378
220 13937614905321
221 15123486893860
222 16407703700967
223 17797557587301
224 19302200299008
225 20930063055637
226 22691820767200
227 24597226459537
228 26658712611305
229 28887565394856
230 31298245029017
231 33903817245979
232 36721077300541
233 39765155116080
234 43055534646031
235 46609741634863
236 50450350351004
237 54597664845444
238 59077811659302
239 63914318302713
240 69137388085511
241 74774284167889
242 80859889285180
243 87425798172620
244 94512256013969
245 102155874190514
246 110403045673026
247 119296192549559
248 128888745611470
249 139229850626186
250 150380996959050
251 162399111155815
252 175354899602959
253 189314280974353
254 204358506434242
255 220563888670796
256 238023728420247
257 256826337245919
258 277078791897963
259 298883253273669
260 322362530449201
261 347634753167582
262 374840702103480
263 404116915537126
264 435624688719076
265 469521753570380
266 505992828525682
267 545220045365678
268 587414842987657
269 632787409879613
270 681579681860236
271 734034097271542
272 790427371089139
273 851038978039095
274 916185303547723
275 986188339134464
276 1061409698276939
277 1142220126440850
278 1229032810499380
279 1322274390231454
280 1422416823718468
281 1529950765909528
282 1645415170566172
283 1769373976603901
284 1902442463854720
285 2045268399776163
286 2198554029315331
287 2363042968040294
288 2539536512790789
289 2728887770335699
290 2932010861067017
291 3149883931873240
292 3383549551043986
293 3634128544128362
294 3902809736728178
295 4190876685165722
296 4499684677418071
297 4830702750169742
298 5185475643101584
299 5565683711190080
300 5973087244987948
301 6409607180076235
302 6877249032612725
303 7378207545382127
304 7914767108604912
305 8489433880543225
306 9104809385103413
307 9763753819853501
308 10469229213146194
309 11224498046211417
310 12032932091500504
311 12898250746307552
312 13824291355624676
313 14815291994327146
314 15875618912591365
315 17010098775714207
316 18223698476254308
317 19521912261370878
318 20910389022843054
319 22395379892153815
320 23983307864470830
321 25681281836833090
322 27496603237892118
323 29437352703200136
324 31511828182062781
325 33729210679329769
326 36098928326207226
327 38631407759193955
328 41337358445768671
329 44228616520782616
330 47317343783787761
331 50616970750890682
332 54141304815158464
333 57905579375390754
334 61925465831268856
335 66218235566193045
336 70801670729909572
337 75695345645853883
338 80919431862375987
339 86496105264767227
340 92448241344253446
341 98800953939389500
342 105580177470169214
343 112814342611417647
344 120532843169564857
345 128767853285743819
346 137552677733732179
347 146923714392989762
348 156918688128756785
349 167578761069084759
350 178946651877444686
351 191068895112337674
352 203993849592762308
353 217774106471497527
354 232464392582884522
355 248124125072367887
356 264815218292285021
357 282604780525802681
358 301562835829403989
359 321765156084619196
360 343290912682531058
361 366225634072558485
362 390658805843929907
363 416686940972499859
364 444411151346709444
365 473940313972902714
366 505388641591685747
367 538878924396498946
368 574540133021387016
369 612510710386016889
370 652936246055415413
371 695972788231182193
372 741784635450624111
373 790547632749760273
374 842447133519859822
375 897681238379123977
376 956458988568301524
377 1019003498723199254
378 1085550451420409005
379 1156351068690117283
380 1231670987438051730
381 1311793005846118225
382 1397016429310716277
383 1487659520344373451
384 1584059416573842722
385 1686574202945320656
386 1795583514607934423
387 1911490141642405381
388 2034721443874425372
389 2165730386820656512
390 2304997908435169006
391 2453033275785600451
392 2610377559722293018
393 2777603188911589346
394 2955318703453601726
395 3144167372562171138
396 3344833416354947637
397 3558039539679131660
398 3784554827692313522
399 4025191037452396890
400 4280812393661937649
401 4552330464459897344
402 4840716101753907822
403 5146992716968485596
404 5472250632889367480
405 5817638559230173466
406 6184380642927034038
407 6573765932563538213
408 6987168438493481548
409 7426034359707170681
410 7891905485834961288
411 8386403950171636939
412 8911259332363532311
413 9468290685860107332
414 10059437721592251093
415 10686739850747783521
416 11352371857188486250
417 12058619682602035477
418 12807921017638532978
419 13602837551717095522
420 14446100941105817842
421 15340581235024348616
422 16289338700163780973
423 17295588134617729472
424 18362757056820614213
425 19494445612326915938
426 20694491655005148586
427 21966925958271111927
428 23316044743565582374
429 24746359907573784139
430 26262679570338692337
431 27870053045249873024
432 29573860004090155940
433 31379749925407948222
434 33293740487030919319
435 35322151255193303186
436 37471711936121677101
437 39749490089118082055
438 42163009876247548542
439 44720173624105212546
440 47429391726275339891
441 50299497914777321997
442 53339890969250364998
443 56560443619740776137
444 59971656724839336793
445 63584561782610184353
446 67410888229858068537
447 71462959622229189534
448 75753874703716338562
449 80297397398199141892
450 85108152275760173631
451 90201508609242920842
452 95593790850132832599
453 101302157115018498895
454 107344825244189563074
455 113740946231399187312
456 120510846408751338056
457 127675896479462960685
458 135258770317274693503
459 143283310452153328942
460 151774803921747529114
461 160759845253930083757
462 170266629731345169189
463 180324815151438915991
464 190965832796682618830
465 202222749499794682925
466 214130596507226401646
467 226726233677637818266
468 240048696333408695481
469 254139063725196268655
470 269040823839833337728
471 284799748632796293944
472 301464276634638726037
473 319085397838246449621
474 337717053790565354310
475 357416035463100270690
476 378242400367732515743
477 400259387208993182768
478 423533849368407255466
479 448136190679782832139
480 474140814447302751831
481 501626085244544477951
482 530674792416000686207
483 561374143447162111635
484 593816240679402322401
485 628098112481464343057
486 664322201661494138995
487 702596441424920491800
488 743034753730293956276
489 785757177829255075535
490 830890376526627788768
491 878567826000472002625
492 928930327665299951104
493 982126268909754046189
494 1038312137970231042330
495 1097652866276098212288
496 1160322343444146479966
497 1226503853040292964346
498 1296390584502345375831
499 1370186175327719747461
500 1448105216448370678336
501 1530373915151020510730
502 1617230590108294674649
503 1708926470745126532480
504 1805726177854950389811
505 1907908676599860770253
506 2015767738367757348131
507 2129613066201770870065
508 2249770733287774404952
509 2376584501326658015941
510 2510416230818789645744
511 2651647414695991329462
512 2800679555393483013200
513 2957935938013368960457
514 3123861969012055686728
515 3298927215239995361970
516 3483625698999132208969
517 3678478231488397266866
518 3884032658989915313782
519 4100866521580728879293
520 4329587245256089399174
521 4570835159268572582012
522 4825283629196036348825
523 5093642468844081402541
524 5376658009576151185753
525 5675116945515613083709
526 5989846334890776534047
527 6321717920187416830323
528 6671648057873861343030
529 7040602558243567280705
530 7429596540730997047706
531 7839699841413377692472
532 8272036792110356032310
533 8727792246997134196188
534 9208211285010299364557
535 9714605910552824253385
536 10248354680293386508795
537 10810910136799991308782
538 11403798362734672435284
539 12028627210193182808541
540 12687085787554397256581
541 13380953551516707875374
542 14112099734630356004977
543 14882493371349645428609
544 15694202677367173190872
545 16549406085703694651113
546 17450391592744986621721
547 18399568885090357527074
548 19399468671447580549821
549 20452755986133647781881
550 21562229530980341429481
551 22730836246595748425988
552 23961670694064803825859
553 25257990990720801175737
554 26623218268047751313271
555 28060954074424868909503
556 29574979952920217453901
557 31169276419748894927439
558 32848022714189426244893
559 34615617467722297226167
560 36476678687724980578783
561 38436066239183540548355
562 40498882134653869255188
563 42670494957365196467086
564 44956540541891121630208
565 47362948475086967814915
566 49895943265636365690693
567 52562073066932153719713
568 55368211448630654679901
569 58321588494138894249416
570 61429793304437998495224
571 64700807631341093991993
572 68143009262545114769838
573 71765208361409728000018
574 75576651903358746656919
575 79587062902550332117261
576 83806646092836271410677
577 88246130232491052293224
578 92916775249007221792332
579 97830417823966056156799
580 102999480249223399885568
581 108437019506381939752002
582 114156738113748322321331
583 120173036927366540319914
584 126501028292630369684068
585 133156592808109314747981
586 140156395134304535527521
587 147517944976056618502519
588 155259615942734665325691
589 163400711021637143225177
590 171961484930545261709458
591 180963214371632229531469
592 190428224367679837751443
593 200379963605642078771090
594 210843035303850058813203
595 221843277974702294747476
596 233407801430629446142460
597 245565073318763942477174
598 258344960940450195602202
599 271778823935171411038901
600 285899562660593357713126
601 300741717431169117291429
602 316341524285515387361767
603 332737021214738767708955
604 349968112229878875132353
605 368076681049112306450897
606 387106664472712518378097
607 407104174034536510701169
608 428117579793802630305958
609 450197640497920868286505
610 473397599012473549284848
611 497773321586983268264382
612 523383406264836525743541
613 550289331894820817431109
614 578555580994819306688250
615 608249799206976703262935
616 639442934230891891433379
617 672209406483365268028552
618 706627265872141875647704
619 742778374489501122010541
620 780748583164253039956135
621 820627927096464809833494
622 862510824307708307258737
623 906496285208936388577670
624 952688135264355810568050
625 1001195239581252046508904
626 1052131752316074289457705
627 1105617357480322732283233
628 1161777547846154605162515
629 1220743883282227392436297
630 1282654302165193484942588
631 1347653398690469326107537
632 1415892770062880919051052
633 1487531314375779362509927
634 1562735617144709179842611
635 1641680271510856351617342
636 1724548307992792550396755
637 1811531538954261222059579
638 1902831035787215034177907
639 1998657499785557450625686
640 2099231791335246290591613
641 2204785329562885169426188
642 2315560678501959954464638
643 2431811978135020889597227
644 2553805592926495884771522
645 2681820577157767944053581
646 2816149391674263895356764
647 2957098406721023291293290
648 3104988693241455332181635
649 3260156566766875853711290
650 3422954460134919385196828
651 3593751512366473093606242
652 3772934530240718164958358
653 3960908626517653864800146
654 4158098278422505135995338
655 4364948020039387909238742
656 4581923606418014062538782
657 4809512765484859587626527
658 5048226477199856578333861
659 5298599790903998161835977
660 5561193229719988602786234
661 5836593679892566690979518
662 6125415931455908060546971
663 6428303646823082911345965
664 6745931049632792619891202
665 7079003980621480904487362
666 7428261747523718330167223
667 7794478277114615270401459
668 8178464140070809216137372
669 8581067809016459006429055
670 9003177873368435296222151
671 9445724414257588946921518
672 9909681425581110438672159
673 10396068317818879739083994
674 10905952562812358606517975
675 11440451339755494136461570
676 12000734422613644982469410
677 12588025982958192698611564
678 13203607740445562865096370
679 13848820938689069774673019
680 14525069780839131203670452
681 15233823596364327376127540
682 15976620585526337949806258
683 16755070196781721611898405
684 17570857205831884392914313
685 18425744325379696331014090
686 19321576646474622748021300
687 20260284504573101134514560
688 21243888313097436591293940
689 22274501712180019193029730
690 23354336826731633633352112
691 24485707726910224719285256
692 25671036145558152756267731
693 26912855282352321660341899
694 28213816018243024349931933
695 29576691098430996373330079
696 31004381884434098018957623
697 32499922954526986150257427
698 34066489437300823491154645
699 35707402072014898214181281
700 37426135171013703439072182
701 39226322186608697857141515
702 41111764353504451272635893
703 43086436813380108729730568
704 45154497992571657248267703
705 47320296340492218542526444
706 49588380502251064973656026
707 51963506732473851797064448
708 54450649927337287608650058
709 57055011781262803818718309
710 59782032748043087019384351
711 62637401014329256829361208
712 65627065465153035926679379
713 68757245555150650779414050
714 72034445359882998041447915
715 75465464433389879258424785
716 79057413033319920151838531
717 82817724061736172968092903
718 86754169559230526154564502
719 90874873834967958464271955
720 95188331332729369889137996
721 99703421066038588851389743
722 104429425967502218897765159
723 109376048755589288633983797
724 114553432887776340478672021
725 119972179997202793461251097
726 125643372580045356214118345
727 131578593152940484100938142
728 137789948815777952136938856
729 144290092294536672158546478
730 151092248532366106394136667
731 158210237797428790040049973
732 165658504467826154079960020
733 173452142400252982164047116
734 181606926088095612526724849
735 190139338504312952787964642
736 199066604826996097332391862
737 208406722988981053698580570
738 218178500181404252370325956
739 228401586363269926553846006
740 239096513771195189390361975
741 250284733664605223632112927
742 261988659089032424830519431
743 274231705156968636964178137
744 287038335332931610617517442
745 300434105576372181442332058
746 314445714439364076083495032
747 329101051426561923839444754
748 344429251220989426850633366
749 360460746646995606102048558
750 377227327366361980317507639
751 394762197863745815164228078
752 413100040984418295464818337
753 432277081397974171941061025
754 452331154380606488517967710
755 473301775252180449131086624
756 495230213840323653979373774
757 518159570428471186038321829
758 542134856376390699841756775
759 567203077162850174456541850
760 593413319677808316797051769
761 620816842993128406943049088
762 649467172885788032743400604
763 679420201023937121679955414
764 710734287328479080539222709
765 743470368319995996455126359
766 777692067978181619885456496
767 813465816058171266965701185
768 850860968164017850603492155
769 889949934911026009628744532
770 930808311991061405236062270
771 973515021131137361169997541
772 1018152450995330780209962457
773 1064806610969410515238285634
774 1113567283816893246505518318
775 1164528193405523970791582180
776 1217787170114128167980400733
777 1273446333709649017470807006
778 1331612272587360110224827665
779 1392396243107617214648911648
780 1455914363845411427695082773
781 1522287832804423119846116047
782 1591643137953323013140124507
783 1664112293851955728856659506
784 1739833069862033024449885717
785 1818949247846821292945052896
786 1901610869563554182593950342
787 1987974517234767271020717068
788 2078203581759823202503942808
789 2172468568103658277895898863
790 2270947386105960200305000765
791 2373825682792628785660321568
792 2481297157714513819345174378
793 2593563924459032245003993911
794 2710836852616792425934779456
795 2833335960956833722614107038
796 2961290788300198336335728220
797 3094940821022983215459289838
798 3234535895312007066236557215
799 3380336661876703988217281490
800 3532615022274949835137658471
801 3691654633948805475388289736
802 3857751383539463600466279511
803 4031213935614608972402961601
804 4212364246142102968624249755
805 4401538158549404124883557957
806 4599085960797387966881351319
807 4805373032706823828764886187
808 5020780450368619738089200844
809 5245705688990131350679751425
810 5480563278697799837871792844
811 5725785567499259839372721975
812 5981823432881117953376769977
813 6249147109853094818126347565
814 6528246963119457826376071515
815 6819634385571307832091672800
816 7123842636217688801951947058
817 7441427814923492029242728323
818 7772969771727744174918508436
819 8119073164090449358847415422
820 8480368443704106809961421841
821 8857513003015372327372716804
822 9251192246154173938622995151
823 9662120832038716174362900298
824 10091043836608247568236182052
825 10538738100405367679889199489
826 11006013489906618974963253461
827 11493714358108185634573476932
828 12002720913407284863434103404
829 12533950802399267070998491032
830 13088360595475876872546246653
831 13666947501778062536666554111
832 14270750981449376000432889214
833 14900854603483141772741334601
834 15558387795404885475510029400
835 16244527855610089760751336811
836 16960501852154155881738432688
837 17707588802102196524777916838
838 18487121732083592889147917385
839 19300490038174146005529600711
840 20149141721931324624854318828
841 21034585945406700169306830298
842 21958395457523290744332303713
843 22922209359979568910894789510
844 23927735740069328356289689508
845 24976754664493668631787308069
846 26071121036063422292431951821
847 27212767833790393794754423450
848 28403709212361183533831279090
849 29646044008340726954062465257
850 30941959102872262320239941269
851 32293733215404140522359150175
852 33703740551763723569536066567
853 35174454908520789119917052836
854 36708453630412584151885474457
855 38308422050294719475162564826
856 39977157781871888335192800262
857 41717575522169660719222815183
858 43532711707661413358218887250
859 45425729708334247909248607622
860 47399924877610694038066395214
861 49458730169390584573568821544
862 51605721614658696063834375818
863 53844624395376103910651079948
864 56179318783357459985759109357
865 58613846707573495221526229740
866 61152418193788803563657411320
867 63799418464738347528604615870
868 66559414922156029668804818807
869 69437164822417957512054772397
870 72437622845980936252895748991
871 75565949394462941891515977484
872 78827518796169282156759772059
873 82227928274224619703815601126
874 85773006840812852287109590222
875 89468824989907177785006097550
876 93321704337111237779587587013
877 97338228094775572292021015621
878 101525251518925447385686593501
879 105889913229129152298706629828
880 110439646528959225681251210993
881 115182191637915469096062465178
882 120125607957218005411935199402
883 125278287286415087270171571133
884 130648967112079747621012314485
885 136246744887478771694908564653
886 142081092427970970528155815041
887 148161871338313116107058142616
888 154499348605273066847579284237
889 161104213263835196182541452505
890 167987593284782118614979116842
891 175161073578275538004219822368
892 182636714281967643294168089376
893 190427070208213187624323193176
894 198545210646687983717128092472
895 207004740369879893495401804842
896 215819821073265083170651326564
897 225005194062775830534662189473
898 234576203465364324670396222549
899 244548820731906355560142742263
900 254939669761522575619842610853
901 265766053363903248697518295230
902 277045980452114884510510399940
903 288798194619682982505352088945
904 301042203568851410936481283476
905 313798309970000334628821676787
906 327087643305512460397406071448
907 340932193192302295075383990952
908 355354843835650752635344478054
909 370379410009852518522369659718
910 386030674331684890015030607924
911 402334426109523424086312331242
912 419317501662596694807244886571
913 437007826265461493503130837948
914 455434457756950883145109477878
915 474627631824732544710991238737
916 494618809166980598267583611098
917 515440724380962833218185578892
918 537127436961059485584849073923
919 559714384076045288567311465841
920 583238435709253153713721905655
921 607737951631549433608540686420
922 633252841013315793816582611383
923 659824623924185778840386292433
924 687496495772223454136682154660
925 716313393687429007179088115331
926 746322066171165105049987831607
927 777571144748392917163276699958
928 810111219240186016861109410992
929 843994915099779660488227656022
930 879276974753075757452027020458
931 916014341066044144878206679501
932 954266245232632916421853191538
933 994094296856028615440664244855
934 1035562578900527424582706314482
935 1078737744906834024638480165687
936 1123689121564419025596748517014
937 1170488813621619986392270021518
938 1219211814678020918802778228027
939 1269936120393835268456454364978
940 1322742848148123283042807630404
941 1377716359199024282760071376000
942 1434944387903421574846682012669
943 1494518173530306325606484858365
944 1556532599791071367587953036269
945 1621086337062907020507555754424
946 1688281993036537404472645513019
947 1758226266165365229004240392581
948 1831030108299460723369273938042
949 1906808890239506867343011893815
950 1985682577292538314533700394530
951 2067775907877931217428641608069
952 2153218583012118080021295782237
953 2242145458987285963225582689730
954 2334696751869439446687853765081
955 2431018245349510843937770161004
956 2531261511422111281941881978179
957 2635584134593841892901480320062
958 2744149949999297472149013346632
959 2857129285242951836340835530893
960 2974699217304924408839530014437
961 3097043833391387709156632299462
962 3224354508085776391093830339814
963 3356830184688752187286193918385
964 3494677674181463683168899175393
965 3638111958650271302527461782476
966 3787356513747932605629108141288
967 3942643635921139491810003385039
968 4104214790183725858972279108311
969 4272320962997254825227230431378
970 4447223037308190652750824747232
971 4629192173073989569690409959807
972 4818510211664356904702859196924
973 5015470086178295585934786021003
974 5220376257468851839606018954332
975 5433545156561159579109643270269
976 5655305654731283515360194693682
977 5885999540512335087372970808454
978 6125982026442036380028853909499
979 6375622263334395015551143580742
980 6635303886508379854279369245466
981 6905425570207429605414123365245
982 7186401616334173562367398568489
983 7478662552120272152097292985219
984 7782655764620519149420188800318
985 8098846144972326016768701613937
986 8427716772147982942513533561071
987 8769769607397722837337728800602
988 9125526231022648605262917045008
989 9495528590869075769268360405379
990 9880339796168007060294793334596
991 10280544924242760129056380931515
992 10696751875765328384651316503167
993 11129592244155680718937239539522
994 11579722236932449753228587489191
995 12047823612622361059231771873848
996 12534604673234093904600759181471
997 13040801273861817694784986989319
998 13567177891688571764688827117365
999 14114528713860716475528942076600
1000 14683678788832685475684199561111