0 1
1 1
2 1
3 3
4 3
5 5
6 8
7 10
8 13
9 18
10 27
11 32
12 44
13 55
14 73
15 97
16 121
17 151
18 194
19 240
20 299
21 384
22 465
23 576
24 706
25 869
26 1051
27 1293
28 1572
29 1896
30 2290
31 2761
32 3302
33 3973
34 4732
35 5645
36 6759
37 7995
38 9477
39 11218
40 13258
41 15597
42 18393
43 21565
44 25319
45 29703
46 34701
47 40478
48 47278
49 54985
50 63955
51 74275
52 86156
53 99723
54 115455
55 133467
56 153978
57 177595
58 204481
59 235229
60 270402
61 310439
62 355903
63 407970
64 466846
65 533947
66 610258
67 696549
68 794283
69 905396
70 1030716
71 1172654
72 1333005
73 1514149
74 1718150
75 1948957
76 2208195
77 2500598
78 2830092
79 3199838
80 3615514
81 4083063
82 4607201
83 5195314
84 5855223
85 6593997
86 7421567
87 8348103
88 9384082
89 10541924
90 11837340
91 13282964
92 14895970
93 16696607
94 18704012
95 20940498
96 23433676
97 26207497
98 29295632
99 32730498
100 36549492
101 40791935
102 45507822
103 50740249
104 56548734
105 62994076
106 70138511
107 78056048
108 86831688
109 96546452
110 107301921
111 119204455
112 132367412
113 146920791
114 163008871
115 180779333
116 200403667
117 222072413
118 245979897
119 272354054
120 301443624
121 333501852
122 368829089
123 407750098
124 450601009
125 497773998
126 549687104
127 606788964
128 669580348
129 738618468
130 814476023
131 897818836
132 989351930
133 1089844195
134 1200133047
135 1321163247
136 1453905502
137 1599463832
138 1759035979
139 1933906595
140 2125485632
141 2335331346
142 2565080227
143 2816578180
144 3091805639
145 3392900624
146 3722203264
147 4082289047
148 4475884738
149 4906013204
150 5375958694
151 5889233741
152 6449705363
153 7061586055
154 7729346236
155 8457957643
156 9252775520
157 10119547135
158 11064578606
159 12094714291
160 13217290652
161 14440321981
162 15772523256
163 17223219661
164 18802629964
165 20521784927
166 22392563416
167 24427880320
168 26641796129
169 29049282022
170 31666793668
171 34512029960
172 37604019810
173 40963477882
174 44612840620
175 48576108716
176 52879488020
177 57551164770
178 62621530120
179 68123475385
180 74092647046
181 80567151035
182 87588502218
183 95201378497
184 103453826186
185 112397852501
186 122089634798
187 132589386170
188 143962426254
189 156279050267
190 169614857992
191 184051418373
192 199676902573
193 216585706994
194 234880035638
195 254669854727
196 276073248542
197 299217655910
198 324240405595
199 351288714951
200 380521550565
201 412109904228
202 446237227055
203 483101377554
204 522915089249
205 565906651567
206 612321882309
207 662425264222
208 716500182139
209 774852051389
210 837808876779
211 905722282197
212 978970762383
213 1057961000916
214 1143128496911
215 1234942086526
216 1333904692092
217 1440555630088
218 1555474207607
219 1679282527352
220 1812646557938
221 1956282238832
222 2110957087294
223 2277493531573
224 2456774169623
225 2649745982440
226 2857422100611
227 3080890523036
228 3321316827329
229 3579949092096
230 3858125647334
231 4157280848309
232 4478948518751
233 4824774661712
234 5196520747131
235 5596071960954
236 6025447783457
237 6486811173580
238 6982474158584
239 7514914301931
240 8086782139398
241 8700912089520
242 9360338386311
243 10068307522946
244 10828288491189
245 11643995117677
246 12519397817878
247 13458739331085
248 14466558663393
249 15547707862463
250 16707369775527
251 17951086514768
252 19284780953254
253 20714777688235
254 22247836942935
255 23891181097032
256 25652519810145
257 27540091333367
258 29562693619050
259 31729715121368
260 34051185264287
261 36537809760438
262 39201011781831
263 42052987207629
264 45106752702278
265 48376190971848
266 51876120949198
267 55622350582417
268 59631738300675
269 63922269674507
270 68513128738953
271 73424763395895
272 78678986231657
273 84299051695689
274 90309743730489
275 96737486869229
276 103610448442547
277 110958633958420
278 118814032518967
279 127210723751226
280 136185011713908
281 145775576161622
282 156023623907527
283 166973028516165
284 178670530346347
285 191165898798644
286 204512119557802
287 218765612721431
288 233986448039453
289 250238549055620
290 267589973841836
291 286113149496037
292 305885141545287
293 326987964310985
294 349508883050134
295 373540717568829
296 399182227211327
297 426538458238906
298 455721120768224
299 486849032833044
300 520048548726688
301 555453993294482
302 593208208929971
303 633463047712714
304 676379909166540
305 722130369471579
306 770896784753696
307 822872923753937
308 878264719680253
309 937290983386200
310 1000184164822618
311 1067191237539909
312 1138574552338106
313 1214612743970596
314 1295601775986205
315 1381855964287398
316 1473709044644224
317 1571515422914588
318 1675651379261656
319 1786516353476275
320 1904534408114302
321 2030155672331217
322 2163857859470719
323 2306148011155506
324 2457564194020256
325 2618677325220667
326 2790093196120942
327 2972454542224242
328 3166443147841514
329 3372782299826812
330 3592239170584971
331 3825627390657808
332 4073809875133916
333 4337701714734558
334 4618273154250099
335 4916553007053092
336 5233631990486707
337 5570666346678208
338 5928881771812532
339 6309577470922142
340 6714130333031758
341 7143999664728838
342 7600731886490538
343 8085965577803147
344 8601436944891913
345 9148985477742147
346 9730559800068799
347 10348224230800589
348 11004165347761143
349 11700699000410678
350 12440277937092833
351 13225499650131776
352 14059114547312076
353 14944035041442466
354 15883344679868340
355 16880307919850647
356 17938380664310149
357 19061221174988607
358 20252701458124119
359 21516919780145985
360 22858213400035575
361 24281172077600100
362 25790652697872660
363 27391794350829107
364 29090034139320080
365 30891124435480138
366 32801150536962706
367 34826549364131323
368 36974129620221518
369 39251092630723365
370 41665054256446809
371 44224068610460229
372 46936652495569843
373 49811811185350595
374 52859066214736270
375 56088484111597000
376 59510706626371760
377 63136983347179185
378 66979205406101338
379 71049940937023335
380 75362473358777019
381 79930840795300790
382 84769877819221724
383 89895260113557873
384 95323550865032926
385 101072249518645382
386 107159844227782795
387 113605866047771358
388 120430946252884078
389 127656877456537692
390 135306677366956557
391 143404655573871763
392 151976485391502452
393 161049278090534433
394 170651661459742429
395 180813863394223265
396 191567799112180467
397 202947162654359487
398 214987524968718144
399 227726435447537955
400 241203529356650931
401 255460641875028355
402 270541927287237160
403 286493983984296850
404 303365988091746099
405 321209832188832319
406 340080271781180213
407 360035080672472474
408 381135213538165640
409 403444976215142211
410 427032207625760295
411 451968468667859019
412 478329241723180751
413 506194141938498640
414 535647138253577960
415 566776785335174212
416 599676470442146009
417 634444670403359994
418 671185222629662565
419 710007611888471141
420 751027270501152117
421 794365893225217597
422 840151771940562030
423 888520144429357565
424 939613561802004877
425 993582277217921347
426 1050584652526698514
427 1110787585243079629
428 1174366961352848715
429 1241508127720865593
430 1312406389525416625
431 1387267535868930429
432 1466308390000239006
433 1549757386910698262
434 1637855184896074116
435 1730855304419846050
436 1829024799914710946
437 1932644969896517876
438 2042012099439937731
439 2157438240387112042
440 2279252035992086969
441 2407799583103467382
442 2543445338207827249
443 2686573074443023393
444 2837586882394141918
445 2996912221912901549
446 3164997031976735339
447 3342312892358306950
448 3529356243386831494
449 3726649673579687048
450 3934743266293493743
451 4154216014777309991
452 4385677314095651910
453 4629768523146143901
454 4887164603873142523
455 5158575851025762089
456 5444749700867678318
457 5746472632037112160
458 6064572167326822179
459 6399918970234458910
460 6753429044884184067
461 7126066055155391997
462 7518843750535526274
463 7932828514394509579
464 8369142046202087457
465 8828964170978706552
466 9313535785713353209
467 9824161964877405015
468 10362215207662589119
469 10929138849262124509
470 11526450648522661758
471 12155746546175009089
472 12818704606095119206
473 13517089165353699534
474 14252755175077403132
475 15027652758971828632
476 15843832004817448728
477 16703447984098455654
478 17608766014387270013
479 18562167197434169815
480 19566154212770429198
481 20623357399055296536
482 21736541143904242509
483 22908610576841038708
484 24142618585390946324
485 25441773194087396011
486 26809445283805650205
487 28249176692913617000
488 29764688725095365493
489 31359891059874417807
490 33038891092030416974
491 34806003747829918858
492 36665761755942432463
493 38622926421437830161
494 40682498936330761163
495 42849732224914251833
496 45130143356463198855
497 47529526584728963783
498 50053966992425432000
499 52709854797601767299
500 55503900370016473163
501 58443149951847005239
502 61535002131858892758
503 64787225140165492690
504 68207974946863359302
505 71805814232664765865
506 75589732293090365484
507 79569165874397820204
508 83754021003830085434
509 88154695896017490089
510 92782104924590634274
511 97647703739515217304
512 102763515614374107969
513 108142159019901116576
514 113796876509943059621
515 119741565017379986795
516 125990807557952764335
517 132559906439790741548
518 139464918087224457061
519 146722689479890498449
520 154350896320557281435
521 162368083047415618374
522 170793704704673920360
523 179648170788821978716
524 188952891211827306675
525 198730324390171007691
526 209004027602597569250
527 219798709765153012220
528 231140286649720304942
529 243055938692439620206
530 255574171579128615409
531 268724879615936803153
532 282539412083576165188
533 297050642746946636842
534 312293042577411901079
535 328302755868282428873
536 345117679978495796317
537 362777548735617597105
538 381324019742342147362
539 400800765806719811283
540 421253570587214776813
541 442730428674593949938
542 465281650416725902595
543 488959971533907567612
544 513820667841479368819
545 539921675355905573654
546 567323715916214434614
547 596090428608178480805
548 626288507373057185175
549 657987844885110167975
550 691261683100937680917
551 726186770826175451279
552 762843528495358672669
553 801316220524408628373
554 841693135723038327752
555 884066775899379174024
556 928534053163489565112
557 975196496376516473625
558 1024160467012798638935
559 1075537384895433787340
560 1129443964425832328271
561 1186002461498584714459
562 1245340931750955180185
563 1307593500717267933760
564 1372900646241339874260
565 1441409493763720808557
566 1513274125237032750439
567 1588655901979568574903
568 1667723802265625449281
569 1750654774393886881253
570 1837634105718071479818
571 1928855808417749751812
572 2024523022972619910831
573 2124848439775756528631
574 2230054739893179974566
575 2340375055932661696424
576 2456053453647803194835
577 2577345435309125250848
578 2704518466029068497917
579 2837852523671117836368
580 2977640673605376827301
581 3124189669549395315267
582 3277820581333612877548
583 3438869450915261913181
584 3607687978130533951548
585 3784644237072852078212
586 3970123424673560344946
587 4164528643091858825610
588 4368281717010420687815
589 4581824047550706828050
590 4805617504690736388312
591 5040145359382259097752
592 5285913257372563406576
593 5543450236786537658996
594 5813309790917592134924
595 6096070978439661841835
596 6392339583388038534926
597 6702749326578255474274
598 7027963130944330950502
599 7368674443471106805745
600 7725608615608304724697
601 8099524345008968947079
602 8491215181571859651094
603 8901511099998464202726
604 9331280142023343219347
605 9781430131746575331847
606 10252910466524401355107
607 10746713987093437530021
608 11263878930660742682419
609 11805490969929428366066
610 12372685342060094023280
611 12966649071929233957217
612 13588623292930640650577
613 14239905670003174130253
614 14921852929623506920944
615 15635883500689708397038
616 16383480271343079932564
617 17166193467340894406328
618 17985643656188818979056
619 18843524883026812726214
620 19741607944281202671540
621 20681743804230980698541
622 21665867160919106933704
623 22696000168534918535540
624 23774256321770796278914
625 24902844509821141303516
626 26084073247622123798377
627 27320355091091650743812
628 28614211244508674334577
629 29968276369136746270347
630 31385303600258805828211
631 32868169782346776944459
632 34419880932099931381701
633 36043577938048461605619
634 37742542507168659393036
635 39520203370023911638260
636 41380142753766300939557
637 43326103135393890761960
638 45361994287596548086373
639 47491900628495537959512
640 49720088888567268135515
641 52051016109337598821468
642 54489337986048548269192
643 57039917569931420834197
644 59707834345864848831583
645 62498393699977533217919
646 65417136794129832978036
647 68469850865780113327965
648 71662579969019580862358
649 75001636176638139944698
650 78493611263320164539767
651 82145388888643043470799
652 85964157301536600293495
653 89957422589569833717200
654 94133022493548968724775
655 98499140812558803898704
656 103064322425023211792342
657 107837488949809989065929
658 112827955074913002334050
659 118045445583304154484705
660 123500113102425204602826
661 129202556609097047828710
662 135163840722464372438561
663 141395515815671077961853
664 147909638981369138309281
665 154718795888509807216305
666 161836123564467867341558
667 169275334142778979220226
668 177050739617934961855971
669 185177277646464920007000
670 193670538439075781614083
671 202546792791040806401240
672 211823021294790784303702
673 221516944785513598520827
674 231647056072522032416546
675 242232653006487639000773
676 253293872939372299146984
677 264851728636823004821860
678 276928145699326166427395
679 289546001556420690630406
680 302729166100966018543995
681 316502544027298349114063
682 330892118945569487726851
683 345924999347641064484017
684 361629466496738978365767
685 378035024322124661694535
686 395172451403719763986534
687 413073855128097716805852
688 431772728107462894273539
689 451304006956887513875970
690 471704133522123754431798
691 493011118660578088588461
692 515264608683217587126383
693 538505954560882476468605
694 562778284011209428744931
695 588126576586494237753848
696 614597741880182239682752
697 642240700981698994131819
698 671106471315966447204890
699 701248254999186429535522
700 732721530858088486623287
701 765584150264383983283817
702 799896436934556053923498
703 835721290858566323633164
704 873124296530010565793748
705 912173835645002494393754
706 952941204455582920324722
707 995500735969642748420800
708 1039929927187815424526017
709 1086309571584142113450149
710 1134723897048374723370258
711 1185260709502125109616516
712 1238011542423849366244124
713 1293071812524626739545249
714 1350540981816637310715739
715 1410522726335377896382408
716 1473125111790405043120792
717 1538460776413972484337579
718 1606647121303779790877253
719 1677806508565323425240570
720 1752066467560350728370175
721 1829559909590627157411320
722 1910425351363657870745500
723 1994807147581499591738649
724 2082855733026179467057329
725 2174727874526992631684641
726 2270586933197330816720543
727 2370603137356511367828258
728 2474953866572979243070499
729 2583823947260838205464513
730 2697405960300205878362973
731 2815900561166784771842801
732 2939516813060910221387746
733 3068472533559375734579884
734 3202994655339401985258819
735 3343319601521124269630591
736 3489693676220477435622015
737 3642373470924161226796960
738 3801626287305311335233717
739 3967730577139094403038923
740 4140976400009417404539072
741 4321665899496460320659026
742 4510113798589850480720310
743 4706647915097260493578170
744 4911609697828382541168009
745 5125354784384501804388702
746 5348253581421568330137790
747 5580691868258122005702766
748 5823071424763356106964871
749 6075810684493833795619892
750 6339345414061661326827785
751 6614129419777886303163128
752 6900635282661697240736118
753 7199355122913462684542931
754 7510801395026332203757712
755 7835507714754047254516183
756 8174029719171448877486531
757 8526945961140026239793792
758 8894858839546735133665575
759 9278395566699442526223996
760 9678209174353240451256466
761 10094979559896657468905976
762 10529414574253016707469243
763 10982251153144866720267566
764 11454256493437595775452820
765 11946229276303094845246103
766 12459000939051707949371481
767 12993436997552395045223805
768 13550438421194486552552411
769 14130943062459115708348673
770 14735927143251599193618325
771 15366406800182728357590379
772 16023439691115914702712123
773 16708126665387473721791582
774 17421613500152185815930622
775 18165092705448165048335135
776 18939805400674688060287320
777 19747043265231758505663822
778 20588150566222330142532798
779 21464526266234739588277869
780 22377626214281023036818072
781 23328965423140523190012375
782 24320120436482244634533788
783 25352731789213158442499373
784 26428506564684784190905906
785 27549221052536075120023247
786 28716723511027177879983958
787 29932937037933160866071865
788 31199862554217234001347445
789 32519581904805012637122034
790 33894261081003461865730996
791 35326153569291332110820311
792 36817603831309475458719230
793 38371050920140288560046302
794 39989032238152666267924728
795 41674187441824640440155821
796 43429262499223365761478566
797 45257113906052838839358458
798 47160713066311153967482070
799 49143150843919479017546161
800 51207642291916324690718417
801 53357531565987506876175879
802 55596297029429164327161614
803 57927556556927000319093230
804 60355073044707470008978978
805 62882760135008012013842513
806 65514688163099350277655822
807 68255090335325018826480035
808 71108369147018706878807651
809 74079103049516690371101360
810 77172053375707586820145310
811 80392171534037615075318184
812 83744606481247587742748819
813 87234712484413634351287497
814 90868057183348354765049734
815 94650429964861758920044870
816 98587850660670507299136186
817 102686578581328103311565597
818 106953121898990008302046342
819 111394247392210165189539098
820 116016990566555816932442643
821 120828666165374549183917343
822 125836879085425384982182838
823 131049535712791439349896429
824 136474855695048467182709446
825 142121384166144328057782745
826 147998004441170196953438252
827 154113951198881243727140926
828 160478824170308101500767099
829 167102602352663399186387554
830 173995658768439543118835887
831 181168775790202562625287263
832 188633161052479346851204346
833 196400463972967198272933428
834 204482792905919042042841277
835 212892732951607036331330096
836 221643364446629269129125715
837 230748282160593528518919762
838 240221615225805859855817407
839 250078047827618765241768308
840 260332840683892912349622861
841 271001853343300701818922487
842 282101567333279995665326152
843 293649110189407130991550334
844 305662280399307534328717323
845 318159573295485249245248610
846 331160207932470138754794611
847 344684154985237551725996244
848 358752165707196047633926978
849 373385801987246377308024712
850 388607467547073681934240398
851 404440440321386832002885808
852 420908906065118192162847029
853 438037993233483752384306478
854 455853809182481442438703340
855 474383477738910299809395458
856 493655178191035197158997909
857 513698185752933322967279041
858 534542913557200534729311201
859 556220956232998832998062358
860 578765135128512013300048433
861 602209545238751868789340924
862 626589603902176042014369848
863 651942101331923833894854651
864 678305253049552808911257166
865 705718754291968993868670585
866 734223836464829266280993999
867 763863325718040419630944377
868 794681703722068651195040497
869 826725170726664733640849441
870 860041710986224044276413414
871 894681160639423515025322411
872 930695278133994468375178566
873 968137817290403831297276307
874 1007064603102019341926644181
875 1047533610372891520359725673
876 1089605045297562047404866717
877 1133341430091495830559703704
878 1178807690784710863288557571
879 1226071248294812125363017142
880 1275202112900306970409565546
881 1326272982239453164202389684
882 1379359342964001407164643341
883 1434539576182301553349758171
884 1491895066831169519446705799
885 1551510317120427572306407722
886 1613473064199760329833504035
887 1677874402202922987995835972
888 1744808908829458865382548975
889 1814374776630339519787477638
890 1886673949170025182062247576
891 1961812262243051451498980070
892 2039899590330287140837865604
893 2121049998486637864078670779
894 2205381899858361177823328147
895 2293018219035805505104765783
896 2384086561454895186373998151
897 2478719389067654272332664427
898 2577054202510684284004136058
899 2679233730008679866204996861
900 2785406123258011424081291964
901 2895725160544758733082422498
902 3010350457360849134181644515
903 3129447684790586955486063547
904 3253188795950439862732433277
905 3381752260775006488904089628
906 3515323309451932848528026578
907 3654094184820024877763413694
908 3798264404056194372687134850
909 3948041029987599631048174127
910 4103638952378292125694643024
911 4265281179552054612353157135
912 4433199140725330998677039656
913 4607632999438185879260584206
914 4788831978485262229813197494
915 4977054696761985885271249397
916 5172569518457110596620680719
917 5375654915037947398688020587
918 5586599840489707903046717181
919 5805704120287605045099164857
920 6033278854597594500945017540
921 6269646836218075871547032777
922 6515142983794274445372992518
923 6770114790855769535453857535
924 7034922791246284738270935264
925 7309941041535944644572297182
926 7595557621027363849750793908
927 7892175149987280472792690285
928 8200211326759156531920173180
929 8520099484435245357860519726
930 8852289167789622704471519705
931 9197246731199508219591837039
932 9555455958308193170444247516
933 9927418704208016146364144333
934 10313655560950828294318091381
935 10714706547221762476242544441
936 11131131823040446802972003045
937 11563512430385472298061260203
938 12012451060669764654256475183
939 12478572850025558463987287463
940 12962526203393105642219084841
941 13464983648442115491668291257
942 13986642720389808461332339954
943 14528226878818230315841553961
944 15090486457632514352490339875
945 15674199649340090030730863412
946 16280173524874096299762501633
947 16909245090227123414345623717
948 17562282381204278049418164382
949 18240185597652044888424593826
950 18943888278567259077544730359
951 19674358519537677614630201719
952 20432600234018529292004364099
953 21219654460002001376351302502
954 22036600713689328992785822977
955 22884558391833264597669329048
956 23764688224477256883336766846
957 24678193779875802330304627311
958 25626323023444969904306434736
959 26610369932656633959853991290
960 27631676169854671031779959101
961 28691632815042457197824211494
962 29791682160762696600567958704
963 30933319571262081456983090863
964 32118095408212107175145076300
965 33347617025336484671124299334
966 34623550834374989945677089624
967 35947624444900545553602123439
968 37321628880594012723060768053
969 38747420874669028906924951539
970 40226925247235433381852355913
971 41762137367486733856880080167
972 43355125703694480187202475531
973 45008034464098657896377085865
974 46723086331890469574863295781
975 48502585297591744880781425133
976 50348919592252591624428132583
977 52264564725007617011256973527
978 54252086628650374992363617720
979 56314144917015531614209264908
980 58453496258089359289073967747
981 60672997866901472581616944123
982 62975611122393964481889097638
983 65364405312609301711696824965
984 67842561512684535053007916362
985 70413376600297936993484658422
986 73080267413374347463221567597
987 75846775055017741090494764088
988 78716569350814173521193175300
989 81693453463825881865196360981
990 84781368672776248917474449792
991 87984399319118830660869658283
992 91306777928879369941370958005
993 94752890515358301607428526314
994 98327282068994299846820762704
995 102034662240906422414893309844
996 105879911226851315241353110586
997 109868085858568032585527450346
998 114004425909721931667543471911
999 118294360623902162531179843953
1000 122743515472386962786998080157