0 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 2
9 2
10 2
11 2
12 3
13 3
14 3
15 4
16 4
17 5
18 5
19 6
20 6
21 7
22 8
23 8
24 9
25 10
26 11
27 13
28 14
29 15
30 17
31 19
32 21
33 23
34 25
35 28
36 30
37 34
38 37
39 41
40 45
41 49
42 54
43 60
44 66
45 72
46 80
47 88
48 97
49 106
50 117
51 129
52 142
53 156
54 171
55 189
56 207
57 228
58 251
59 276
60 304
61 334
62 368
63 405
64 445
65 490
66 539
67 593
68 652
69 717
70 789
71 868
72 955
73 1051
74 1156
75 1271
76 1399
77 1538
78 1692
79 1862
80 2048
81 2253
82 2478
83 2726
84 2999
85 3298
86 3628
87 3991
88 4390
89 4830
90 5313
91 5844
92 6428
93 7071
94 7778
95 8556
96 9412
97 10353
98 11388
99 12527
100 13780
101 15158
102 16674
103 18341
104 20176
105 22193
106 24413
107 26854
108 29539
109 32493
110 35743
111 39317
112 43249
113 47574
114 52331
115 57565
116 63321
117 69653
118 76619
119 84280
120 92709
121 101979
122 112177
123 123395
124 135735
125 149308
126 164239
127 180663
128 198730
129 218603
130 240463
131 264509
132 290960
133 320056
134 352062
135 387268
136 425995
137 468595
138 515454
139 567000
140 623700
141 686070
142 754677
143 830145
144 913159
145 1004475
146 1104923
147 1215415
148 1336956
149 1470652
150 1617717
151 1779489
152 1957438
153 2153182
154 2368500
155 2605350
156 2865885
157 3152474
158 3467721
159 3814494
160 4195943
161 4615537
162 5077091
163 5584800
164 6143280
165 6757608
166 7433369
167 8176706
168 8994377
169 9893815
170 10883196
171 11971516
172 13168667
173 14485534
174 15934088
175 17527497
176 19280246
177 21208271
178 23329098
179 25662008
180 28228209
181 31051030
182 34156133
183 37571746
184 41328921
185 45461813
186 50007994
187 55008794
188 60509673
189 66560640
190 73216704
191 80538375
192 88592213
193 97451434
194 107196577
195 117916235
196 129707859
197 142678644
198 156946509
199 172641160
200 189905276
201 208895804
202 229785384
203 252763922
204 278040315
205 305844346
206 336428781
207 370071659
208 407078825
209 447786708
210 492565378
211 541821916
212 596004108
213 655604519
214 721164971
215 793281468
216 872609615
217 959870576
218 1055857634
219 1161443397
220 1277587737
221 1405346511
222 1545881162
223 1700469278
224 1870516206
225 2057567827
226 2263324610
227 2489657071
228 2738622778
229 3012485056
230 3313733561
231 3645106918
232 4009617609
233 4410579370
234 4851637308
235 5336801038
236 5870481142
237 6457529257
238 7103282182
239 7813610400
240 8594971441
241 9454468585
242 10399915443
243 11439906988
244 12583897686
245 13842287455
246 15226516201
247 16749167821
248 18424084603
249 20266493063
250 22293142370
251 24522456607
252 26974702267
253 29672172494
254 32639389743
255 35903328718
256 39493661590
257 43443027749
258 47787330524
259 52566063576
260 57822669934
261 63604936927
262 69965430620
263 76961973682
264 84658171050
265 93123988155
266 102436386971
267 112680025668
268 123948028235
269 136342831058
270 149977114164
271 164974825581
272 181472308139
273 199619538953
274 219581492848
275 241539642133
276 265693606346
277 292262966981
278 321489263679
279 353638190047
280 389002009052
281 427902209957
282 470692430953
283 517761674048
284 569537841453
285 626491625599
286 689140788159
287 758054866975
288 833860353672
289 917246389039
290 1008971027943
291 1109868130738
292 1220854943811
293 1342940438193
294 1477234482012
295 1624957930213
296 1787453723235
297 1966199095558
298 2162819005114
299 2379100905625
300 2617010996188
301 2878712095807
302 3166583305387
303 3483241635926
304 3831565799519
305 4214722379471
306 4636194617418
307 5099814079160
308 5609795487076
309 6170775035784
310 6787852539362
311 7466637793298
312 8213301572628
313 9034631729891
314 9938094902880
315 10931904393168
316 12025094832485
317 13227604315734
318 14550364747307
319 16005401222038
320 17605941344241
321 19366535478666
322 21303189026532
323 23433507929186
324 25776858722104
325 28354544594315
326 31189999053746
327 34308998959121
328 37739898855033
329 41513888740536
330 45665277614590
331 50231805376049
332 55254985913654
333 60780484505020
334 66858532955522
335 73544386251074
336 80898824876181
337 88988707363799
338 97887578100179
339 107676335910197
340 118443969501217
341 130288366451339
342 143317203096473
343 157648923406120
344 173413815746732
345 190755197321405
346 209830717053546
347 230813788758901
348 253895167634791
349 279284684398270
350 307213152838097
351 337934468121907
352 371727914934097
353 408900706427507
354 449790777070258
355 494769854777284
356 544246840255012
357 598671524280513
358 658538676708565
359 724392544379421
360 796831798817363
361 876514978699100
362 964166476569010
363 1060583124225911
364 1166641436648502
365 1283305580313352
366 1411636138344687
367 1552799752179156
368 1708079727397072
369 1878887700136779
370 2066776470150457
371 2273454117165503
372 2500799528882053
373 2750879481770259
374 3025967429947285
375 3328564172942013
376 3661420590236214
377 4027562649259836
378 4430318914185820
379 4873350805604402
380 5360685886164842
381 5896754474781326
382 6486429922259459
383 7135072914485405
384 7848580205933945
385 8633438226527340
386 9496782049180074
387 10446460254098081
388 11491106279507889
389 12640216907458678
390 13904238598204546
391 15294662458025001
392 16824128703827501
393 18506541574210251
394 20357195731631276
395 22392915304794404
396 24632206835273844
397 27095427518801229
398 29804970270681351
399 32785467297749487
400 36064014027524435
401 39670415430276879
402 43637456973304567
403 48001202670635024
404 52801322937698526
405 58081455231468379
406 63889600754615217
407 70278560830076738
408 77306416913084412
409 85037058604392853
410 93540764464832139
411 102894840911315353
412 113184325002446888
413 124502757502691577
414 136953033252960735
415 150648336578256808
416 165713170236082489
417 182284487259690738
418 200512935985659812
419 220564229584225793
420 242620652542648373
421 266882717796913210
422 293570989576604531
423 322928088534264984
424 355220897387691482
425 390742987126460631
426 429817285839106694
427 472799014423017363
428 520078915865319100
429 572086807451851010
430 629295488197036111
431 692225037016739722
432 761447540718413694
433 837592294790255063
434 921351524269280570
435 1013486676696208627
436 1114835344365829490
437 1226318878802412439
438 1348950766682653683
439 1483845843350919051
440 1632230427686010956
441 1795453470454612052
442 1974998817500073257
443 2172498699250080583
444 2389748569175088641
445 2628723426092597505
446 2891595768701857256
447 3180755345572042981
448 3498830880129247279
449 3848713968142172007
450 4233585364956389208
451 4656943901452028129
452 5122638291597230942
453 5634902120756954036
454 6198392332832649440
455 6818231566115914384
456 7500054722727505822
457 8250060195000256405
458 9075066214500282045
459 9982572835950310250
460 10980830119545341275
461 12078913131499875402
462 13286804444649862943
463 14615484889114849237
464 16077033378026334161
465 17684736715828967577
466 19453210387411864334
467 21398531426153050768
468 23538384568768355845
469 25892223025645191429
470 28481445328209710572
471 31329589861030681629
472 34462548847133749792
473 37908803731847124772
474 41699684105031837249
475 45869652515535020974
476 50456617767088523071
477 55502279543797375379
478 61052507498177112916
479 67157758247994824208
480 73873534072794306629
481 81260887480073737292
482 89386976228081111021
483 98325673850889222123
484 108158241235978144336
485 118974065359575958769
486 130871471895533554646
487 143958619085086910111
488 158354480993595601122
489 174189929092955161234
490 191608922002250677358
491 210769814202475745094
492 231846795622723319603
493 255031475184995651564
494 280534622703495216720
495 308588084973844738392
496 339446893471229212231
497 373391582818352133455
498 410730741100187346800
499 451803815210206081480
500 496984196731226689628
501 546682616404349358591
502 601350878044784294450
503 661485965849262723895
504 727634562434188996285
505 800398018677607895913
506 880437820545368685505
507 968481602599905554055
508 1065329762859896109461
509 1171862739145885720407
510 1289049013060474292448
511 1417953914366521721693
512 1559749305803173893862
513 1715724236383491283248
514 1887296660021840411573
515 2076026326024024452730
516 2283628958626426898004
517 2511991854489069587804
518 2763191039937976546584
519 3039510143931774201243
520 3343461158324951621367
521 3677807274157446783504
522 4045588001573191461854
523 4450146801730510608040
524 4895161481903561668844
525 5384677630093917835728
526 5923145393103309619301
527 6515459932413640581231
528 7167005925655004639355
529 7883706518220505103290
530 8672077170042555613619
531 9539284887046811174981
532 10493213375751492292479
533 11542534713326641521727
534 12696788184659305673900
535 13966467003125236241290
536 15363113703437759865419
537 16899425073781535851961
538 18589367581159689437157
539 20448304339275658380873
540 22493134773203224218961
541 24742448250523546640857
542 27216693075575901304942
543 29938362383133491435437
544 32932198621446840578980
545 36225418483591524636878
546 39847960331950677100566
547 43832756365145744810623
548 48216032001660319291685
549 53037635201826351220854
550 58341398722008986342939
551 64175538594209884977233
552 70593092453630873474957
553 77652401698993960822452
554 85417641868893356904698
555 93959406055782692595168
556 103355346661360961854684
557 113690881327497058040153
558 125059969460246763844168
559 137565966406271440228585
560 151322563046898584251444
561 166454819351588442676588
562 183100301286747286944247
563 201410331415422015638672
564 221551364556964217202539
565 243706501012660638922793
566 268077151113926702815072
567 294884866225319373096579
568 324373352847851310406237
569 356810688132636441446861
570 392491756945900085591547
571 431740932640490094150702
572 474915025904539103565772
573 522406528494993013922350
574 574647181344492315314585
575 632111899478941546846043
576 695323089426835701530648
577 764855398369519271683712
578 841340938206471198852084
579 925475032027118318737292
580 1018022535229830150611021
581 1119824788752813165672124
582 1231807267628094482239336
583 1354987994390903930463270
584 1490486793829994323509597
585 1639535473212993755860556
586 1803489020534293131446612
587 1983837922587722444591273
588 2182221714846494689050401
589 2400443886331144157955441
590 2640488274964258573750985
591 2904537102460684431126083
592 3194990812706752874238692
593 3514489893977428161662561
594 3865938883375170977828817
595 4252532771712688075611699
596 4677786048883956883172869
597 5145564653772352571490156
598 5660121119149587828639171
599 6226133231064546611503089
600 6848746554171001272653397
601 7533621209588101399918737
602 8286983330546911539910611
603 9115681663601602693901672
604 10027249829961762963291839
605 11029974812957939259621023
606 12132972294253733185583126
607 13346269523679106504141438
608 14680896476047017154555582
609 16148986123651718870011141
610 17763884736016890757012255
611 19540273209618579832713480
612 21494300530580437815984828
613 23643730583638481597583311
614 26008103642002329757341642
615 28608914006202562733075807
616 31469805406822819006383387
617 34616785947505100907021726
618 38078464542255610997723899
619 41886310996481172097496289
620 46074942096129289307245917
621 50682436305742218237970509
622 55750679936316440061767560
623 61325747929948084067944316
624 67458322722942892474738748
625 74204154995237181722212623
626 81624570494760899894433885
627 89787027544236989883877274
628 98765730298660688872265001
629 108642303328526757759491501
630 119506533661379433535440651
631 131457187027517376888984717
632 144602905730269114577883188
633 159063196303296026035671507
634 174969515933625628639238658
635 192466467526988191503162524
636 211713114279687010653478776
637 232884425707655711718826654
638 256172868278421282890709319
639 281790155106263411179780251
640 309969170616889752297758277
641 340966087678578727527534104
642 375062696446436600280287515
643 412568966091080260308316266
644 453825862700188286339147893
645 499208448970207114973062682
646 549129293867227826470368951
647 604042223253950609117405846
648 664446445579345670029146430
649 730891090137280237032061073
650 803980199151008260735267181
651 884378219066109086808793899
652 972816040972719995489673289
653 1070097645069991995038640618
654 1177107409576991194542504680
655 1294818150534690313996755148
656 1424299965588159345396430662
657 1566729962146975279936073729
658 1723402958361672807929681102
659 1895743254197840088722649212
660 2085317579617624097594914133
661 2293849337579386507354405547
662 2523234271337325158089846101
663 2775557698471057673898830711
664 3053113468318163441288713783
665 3358424815149979785417585161
666 3694267296664977763959343677
667 4063694026331475540355278045
668 4470063428964623094390805849
669 4917069771861085403829886434
670 5408776749047193944212875078
671 5949654423951913338634162586
672 6544619866347104672497578844
673 7199081852981815139747336729
674 7918990038279996653722070402
675 8710889042107996319094277442
676 9581977946318795951003705186
677 10540175740950675546104075705
678 11594193315045743100714483275
679 12753612646550317410785931603
680 14028973911205349151864524763
681 15431871302325884067050977240
682 16975058432558472473756074964
683 18672564275814319721131682460
684 20539820703395751693244850706
685 22593802773735326862569335777
686 24853183051108859548826269355
687 27338501356219745503708896290
688 30072351491841720054079785919
689 33079586641025892059487764511
690 36387545305128481265436540962
691 40026299835641329391980195058
692 44028929819205462331178214564
693 48431822801126008564296036021
694 53275005081238609420725639623
695 58602505589362470362798203585
696 64462756148298717399078023944
697 70909031763128589138985826338
698 77999934939441448052884408972
699 85799928433385592858172849870
700 94379921276724152143990134857
701 103817913404396567358389148342
702 114199704744836224094228063177
703 125619675219319846503650869494
704 138181642741251831154015956444
705 151999807015377014269417552088
706 167199787716914715696359307297
707 183919766488606187265995238027
708 202311743137466805992594761829
709 222542917451213486591854238012
710 244797209196334835251039661814
711 269276930115968318776143627995
712 296204623127565150653757990795
713 325825085440321665719133789874
714 358407593984353832291047168862
715 394248353382789215520151885748
716 433673188721068137072167074323
717 477040507593174950779383781755
718 524744558352492445857322159931
719 577219014187741690443054375924
720 634940915606515859487359813516
721 698435007167167445436095794868
722 768278507883884189979705374355
723 845106358672272608977675911790
724 929616994539499869875443502969
725 1022578693993449856862987853266
726 1124836563392794842549286638593
727 1237320219732074326804215302452
728 1361052241705281759484636832698
729 1497157465875809935433100515968
730 1646873212463390928976410567564
731 1811560533709730021874051624321
732 1992716587080703024061456786753
733 2191988245788773326467602465428
734 2411187070367650659114362711971
735 2652305777404415725025798983168
736 2917536355144857297528378881485
737 3209289990659343027281216769634
738 3530218989725277330009338446597
739 3883240888697805063010272291257
740 4271564977567585569311299520383
741 4698721475324344126242429472421
742 5168593622856778538866672419663
743 5685452985142456392753339661630
744 6253998283656702032028673627793
745 6879398112022372235231540990572
746 7567337923224609458754695089629
747 8324071715547070404630164598592
748 9156478887101777445093181058451
749 10072126775811955189602499164297
750 11079339453393150708562749080726
751 12187273398732465779419023988799
752 13406000738605712357360926387679
753 14746600812466283593097019026447
754 16221260893712911952406720929092
755 17843386983084203147647393022001
756 19627725681392623462412132324201
757 21590498249531885808653345556621
758 23749548074485074389518680112283
759 26124502881933581828470548123512
760 28736953170126940011317602935863
761 31610648487139634012449363229449
762 34771713335853597413694299552394
763 38248884669438957155063729507634
764 42073773136382852870570102458397
765 46281150450021138157627112704237
766 50909265495023251973389823974661
767 56000192044525577170728806372127
768 61600211248978134887801687009340
769 67760232373875948376581855710274
770 74536255611263543214240041281301
771 81989881172389897535664045409431
772 90188869289628887289230449950374
773 99207756218591776018153494945412
774 109128531840450953619968844439953
775 120041385024496048981965728883949
776 132045523526945653880162301772344
777 145250075879640219268178531949578
778 159775083467604241194996385144536
779 175752591814364665314496023658989
780 193327850995801131845945626024888
781 212660636095381245030540188627377
782 233926699704919369533594207490115
783 257319369675411306486953628239127
784 283051306642952437135648991063039
785 311356437307247680849213890169343
786 342492081037972448934135279186278
787 376741289141769693827548807104905
788 414415418055946663210303687815396
789 455856959861541329531334056596936
790 501442655847695462484467462256629
791 551586921432465008732914208482292
792 606745613575711509606205629330522
793 667420174933282660566826192263574
794 734162192426610926623508811489931
795 807578411669272019285859692638924
796 888336252836199221214445661902817
797 977169878119819143335890228093099
798 1074886865931801057669479250902408
799 1182375552524981163436427175992649
800 1300613107777479279780069893591914
801 1430674418555227207758076882951106
802 1573741860410749928533884571246216
803 1731116046451824921387273028370838
804 1904227651097007413526000331207922
805 2094650416206708154878600364328714
806 2304115457827378970366460400761586
807 2534527003610116867403106440837744
808 2787979703971128554143417084921519
809 3066777674368241409557758793413671
810 3373455441805065550513534672755038
811 3710800985985572105564888140030542
812 4081881084584129316121376954033596
813 4490069193042542247733514649436956
814 4939076112346796472506866114380651
815 5432983723581476119757552725818717
816 5976282095939623731733307998400588
817 6573910305533586104906638798240647
818 7231301336086944715397302678064712
819 7954431469695639186937032945871183
820 8749874616665203105630736240458302
821 9624862078331723416193809864504132
822 10587348286164895757813190850954545
823 11646083114781385333594509936049999
824 12810691426259523866953960929654999
825 14091760568885476253649357022620499
826 15500936625774023879014292724882549
827 17051030288351426266915721997370804
828 18756133317186568893607294197107885
829 20631746648905225782968023616818674
830 22694921313795748361264825978500541
831 24964413445175323197391308576350595
832 27460854789692855517130439433985655
833 30206940268662141068843483377384220
834 33227634295528355175727831715122642
835 36550397725081190693300614886634906
836 40205437497589309762630676375298397
837 44225981247348240738893744012828237
838 48648579372083064812783118414111061
839 53513437309291371294061430255522167
840 58864781040220508423467573281074384
841 64751259144242559265814330609181822
842 71226385058666815192395763670100004
843 78349023564533496711635340037110005
844 86183925920986846382798874040821005
845 94802318513085531021078761444903106
846 104282550364394084123186637589393416
847 114710805400833492535505301348332758
848 126181885940916841789055831483166034
849 138800074535008525967961414631482637
850 152680081988509378564757556094630901
851 167948090187360316421233311704093991
852 184742899206096348063356642874503390
853 203217189126705982869692307161953730
854 223538908039376581156661537878149103
855 245892798843314239272327691665964013
856 270482078727645663199560460832560414
857 297530286600410229519516506915816456
858 327283315260451252471468157607398101
859 360011646786496377718614973368137912
860 396012811465146015490476470704951703
861 435614092611660617039524117775446873
862 479175501872826678743476529552991560
863 527093052060109346617824182508290717
864 579802357266120281279606600759119788
865 637782592992732309407567260835031767
866 701560852292005540348323986918534944
867 771716937521206094383156385610388438
868 848888631273326703821472024171427282
869 933777494400659374203619226588570010
870 1027155243840725311623981149247427011
871 1129870768224797842786379264172169713
872 1242857845047277627065017190589386684
873 1367143629552005389771518909648325352
874 1503857992507205928748670800613157888
875 1654243791757926521623537880674473677
876 1819668170933719173785891668741921044
877 2001634988027091091164480835616113149
878 2201798486829800200280928919177724464
879 2421978335512780220309021811095496910
880 2664176169064058242339923992205046601
881 2930593785970464066573916391425551261
882 3223653164567510473231308030568106388
883 3546018481024261520554438833624917026
884 3900620329126687672609882716987408729
885 4290682362039356439870870988686149602
886 4719750598243292083857958087554764562
887 5191725658067621292243753896310241019
888 5710898223874383421468129285941265120
889 6281988046261821763614942214535391633
890 6910186850888003939976436435988930796
891 7601205535976804333974080079587823875
892 8361326089574484767371488087546606263
893 9197458698531933244108636896301266889
894 10117204568385126568519500585931393578
895 11128925025223639225371450644524532936
896 12241817527746003147908595708976986230
897 13465999280520603462699455279874684853
898 14812599208572663808969400807862153338
899 16293859129429930189866340888648368672
900 17923245042372923208852974977513205539