1 1
2 1
3 2
4 4
5 6
6 8
7 12
8 17
9 25
10 34
11 48
12 64
13 87
14 114
15 151
16 198
17 258
18 332
19 428
20 546
21 695
22 879
23 1108
24 1388
25 1737
26 2159
27 2680
28 3312
29 4082
30 5009
31 6138
32 7492
33 9126
34 11081
35 13429
36 16228
37 19575
38 23547
39 28277
40 33879
41 40520
42 48354
43 57615
44 68509
45 81337
46 96388
47 114055
48 134726
49 158922
50 187155
51 220110
52 258478
53 303139
54 355007
55 415244
56 485046
57 565911
58 659420
59 767510
60 892239
61 1036118
62 1201813
63 1392558
64 1611826
65 1863745
66 2152796
67 2484296
68 2863993
69 3298666
70 3795709
71 4363756
72 5012251
73 5752185
74 6595584
75 7556392
76 8649921
77 9893786
78 11307394
79 12913031
80 14735214
81 16802005
82 19144359
83 21797550
84 24800523
85 28197556
86 32037526
87 36375878
88 41273880
89 46800779
90 53033155
91 60057440
92 67969135
93 76875810
94 86896419
95 98164615
96 110828196
97 125052980
98 141022245
99 158941320
100 179037157
101 201563504
102 226800826
103 255062343
104 286694022
105 322081716
106 361651607
107 405878290
108 455285791
109 510457031
110 572035297
111 640735418
112 717345995
113 802742204
114 897889222
115 1003857207
116 1121825655
117 1253101078
118 1399122989
119 1561484260
120 1741939113
121 1942427016
122 2165082726
123 2412264477
124 2686566824
125 2990853288
126 3328272955
127 3702298764
128 4116747851
129 4575826697
130 5084156656
131 5646826438
132 6269423926
133 6958097836
134 7719596526
135 8561340590
136 9491470499
137 10518931233
138 11653530939
139 12906040299
140 14288263229
141 15813153858
142 17494902517
143 19349072332
144 21392703549
145 23644473876
146 26124823784
147 28856144990
148 31862931229
149 35171998602
150 38812667187
151 42817019535
152 47220117251
153 52060304612
154 57379467774
155 63223389737
156 69642060086
157 76690091096
158 84427085896
159 92918126494
160 102234211605
161 112452827179
162 123658467093
163 135943301193
164 149407791354
165 164161473997
166 180323689880
167 198024498219
168 217405540223
169 238621108254
170 261839164434
171 287242591182
172 315030392646
173 345419154406
174 378644460086
175 414962596200
176 454652217534
177 498016338253
178 545384290198
179 597114044353
180 653594511462
181 715248249721
182 782534162353
183 855950655001
184 936038797626
185 1023386001296
186 1118629722447
187 1222461744856
188 1335632511217
189 1458956108631
190 1593315332742
191 1739667485466
192 1899050291079
193 2072588638245
194 2261501482277
195 2467109682329
196 2690844050409
197 2934254452702
198 3199019190624
199 3486955568159
200 3800030811540
201 4140374334111
202 4510290442186
203 4912272557540
204 5349017991778
205 5823444434686
206 6338707117107
207 6898217917909
208 7505665291293
209 8165036391325
210 8880640196082
211 9657133117837
212 10499545811881
213 11413312808728
214 12404303580828
215 13478856804047
216 14643816336918
217 15906570820468
218 17275095314620
219 18757997047472
220 20364563573748
221 22104815594693
222 23989562630549
223 26030463979799
224 28240093030688
225 30632007582523
226 33220824101957
227 36022298795387
228 39053413300784
229 42332468117285
230 45879181430017
231 49714796731562
232 53862196736392
233 58346027280772
234 63192828564722
235 68431177733065
236 74091839987521
237 80207932592552
238 86815098785168
239 93951696324844
240 101658997539336
241 109981406001589
242 118966686511054
243 128666213983066
244 139135237721251
245 150433167164922
246 162623875421442
247 175776027192493
248 189963427212069
249 205265396414609
250 221767171742866
251 239560337447386
252 258743283622731
253 279421700513820
254 301709104145580
255 325727402598459
256 351607498280706
257 379489936353577
258 409525594513630
259 441876425180654
260 476716245126318
261 514231584628805
262 554622591014270
263 598103999764119
264 644906167950402
265 695276184362975
266 749479050977111
267 807798951483200
268 870540601423148
269 938030697107055
270 1010619457849989
271 1088682280271300
272 1172621499193316
273 1262868275682983
274 1359884606798660
275 1464165479511095
276 1576241163524591
277 1696679667566722
278 1826089354061507
279 1965121739142352
280 2114474473171628
281 2274894531302715
282 2447181609690526
283 2632191759695578
284 2830841256194938
285 3044110735542118
286 3273049599907889
287 3518780726999913
288 3782505482774983
289 4065509079931344
290 4369166280803954
291 4694947491735428
292 5044425248743275
293 5419281146224327
294 5821313210078361
295 6252443772108213
296 6714727848864623
297 7210362087579737
298 7741694284440590
299 8311233544157470
300 8921661088674111
301 9575841790926927
302 10276836444455425
303 11027914852598516
304 11832569751496937
305 12694531659219846
306 13617784669369648
307 14606583290938422
308 15665470357470127
309 16799296117948357
310 18013238537856946
311 19312824934521542
312 20703954981581810
313 22192925219623048
314 23786455115074756
315 25491714818907067
316 27316354675525241
317 29268536649375364
318 31356967729366699
319 33590935496294280
320 35980345924352472
321 38535763621755330
322 41268454594048711
323 44190431757005810
324 47314503297174021
325 50654324131207048
326 54224450578407623
327 58040398524762737
328 62118705211448544
329 66476994956110241
330 71134048961226744
331 76109879551142586
332 81425809016135924
333 87104553442363444
334 93170311733256638
335 99648860242438543
336 106567653254842510
337 113955929781864574
338 121844826942251524
339 130267500445714984
340 139259252490490592
341 148857667648537068
342 159102757094554151
343 170037111815457623
344 181706065207042550
345 194157865764816254
346 207443860332653763
347 221618688694250560
348 236740490035547050
349 252871122149748828
350 270076393985555934
351 288426312506951485
352 307995344546594275
353 328862694728515004
354 351112600234160836
355 374834643606739782
356 400124084471081505
357 427082211497036325
358 455816715599416603
359 486442085850202131
360 519080029226489527
361 553859915834053359
362 590919250876133669
363 630404175190318551
364 672469995786920801
365 717281748414933661
366 765014793773095523
367 815855449617946846
368 870001660592424141
369 927663708278504026
370 989064963528027881
371 1054442683854625767
372 1124048858199603937
373 1198151102165202165
374 1277033606317255258
375 1360998140996406583
376 1450365120563200848
377 1545474730900164593
378 1646688123458324562
379 1754388680097822407
380 1868983352414412818
381 1990904080276271745
382 2120609293714440398
383 2258585503418467668
384 2405348984485600803
385 2561447559260629692
386 2727462484478090921
387 2904010449195228001
388 3091745689355914189
389 3291362226197006430
390 3503596235039316062
391 3729228552477565351
392 3969087329293897508
393 4224050838001933874
394 4495050443217950360
395 4783073744756855795
396 5089167902622333390
397 5414443154888614495
398 5760076538726519016
399 6127315826793158270
400 6517483690444234674
401 6931982103344189878
402 7372296998277344771
403 7840003192239828324
404 8336769594111126146
405 8864364711655845488
406 9424662473818648911
407 10019648386916166531
408 10651426042541349642
409 11322223997839814791
410 12034403048033286096
411 12790463914131245410
412 13593055367995663290
413 14444982820229736024
414 15349217395602063012
415 16308905524282212011
416 17327379076428324791
417 18408166071514273223
418 19555001993079899685
419 20771841743740502192
420 22062872274631416671
421 23432525927946127412
422 24885494530620892302
423 26426744282061898920
424 28061531478271779346
425 29795419119966296576
426 31634294451816436213
427 33584387485607686711
428 35652290559753033591
429 37844978993714582065
430 40169832895650887538
431 42634660188226934818
432 45247720917427793378
433 48017752916379879510
434 50953998896253816735
435 54066235044079385421
436 57364801207564440920
437 60860632755411562779
438 64565294202112875868
439 68491014695305249830
440 72650725464514522407
441 77058099339984542851
442 81727592451329423391
443 86674488226447495520
444 91914943812521382388
445 97466039052533400642
446 103345828152503120384
447 109573394187248262793
448 116168906594691319230
449 123153681822406709044
450 130550247292832787793
451 138382408868417771302
452 146675322001274088700
453 155455566768043210980
454 164751226994627008946
455 174591973692967875550
456 185009153036751196274
457 196035879121952693079
458 207707131763675247013
459 220059859601435298962
460 233133088791512855148
461 246968037587513257568
462 261608237117795401542
463 277099658692937084125
464 293490847985095820154
465 310833066447809127792
466 329180440354786236751
467 348590117865297940077
468 369122434535263689540
469 390841087724773925549
470 413813320365937745822
471 438110114589414315202
472 463806395722989090720
473 490981247213115671272
474 519718137037418990419
475 550105156217089646570
476 582235270057484833063
477 616206582789880792740
478 652122616309277708861
479 690092603751826794159
480 730231798680274702121
481 772661800698901194242
482 817510898347443157890
483 864914430181411015541
484 915015164977764526626
485 967963702068112150327
486 1023918892837104436977
487 1083048284492663432791
488 1145528587254576604249
489 1211546166183280283680
490 1281297558915398976584
491 1354990020654822061125
492 1432842097818233927031
493 1515084231823792528434
494 1601959394567762776443
495 1693723757231975234449
496 1790647394127707256988
497 1893015023388712914708
498 2001126786396189109197
499 2115299067935507732402
500 2235865359162721153546
501 2363177165586749727003
502 2497604962360308506005
503 2639539199312414857474
504 2789391358252397447883
505 2947595065228109685823
506 3114607260529103451542
507 3290909429392538904241
508 3477008896489774846939
509 3673440187454186074955
510 3880766460844314373627
511 4099581014136108337306
512 4330508867486349282802
513 4574208429227679803312
514 4831373247220296115429
515 5102733850424119437259
516 5389059685237902557839
517 5691161151412839754605
518 6009891742550732092474
519 6346150296482357563590
520 6700883361046043253814
521 7075087681098833243328
522 7469812812841101061538
523 7886163871877173960419
524 8325304421709547215199
525 8788459509738093372214
526 9276918858139916563272
527 9792040217414468947818
528 10335252890714993104455
529 10908061437534769197066
530 11512049565688532560723
531 12148884221018937118038
532 12820319884668810457873
533 13528203088295522286704
534 14274477158057558272321
535 15061187198789366259328
536 15890485330281488598669
537 16764636188224139077168
538 17686022702925183647667
539 18657152169614995888885
540 19680662624760474143329
541 20759329543578058014151
542 21896072874608048915449
543 23093964428052365461528
544 24356235635319146755373
545 25686285698136515124944
546 27087690146414697161761
547 28564209825041090497578
548 30119800330692771653218
549 31758621920850966411572
550 33485049918193040485771
551 35303685634741113182136
552 37219367841237481106685
553 39237184808533795860831
554 41362486948981812050362
555 43600900087254126032632
556 45958339391344634422362
557 48441023996074488484702
558 51055492352882763723489
559 53808618341405208389392
560 56707628179942787279953
561 59760118173807851691827
562 62974073342292989093494
563 66357886967070816536010
564 69920381106764397104828
565 73670828124684771194491
566 77618973278854430857649
567 81775058425904059774638
568 86149846892761396851587
569 90754649572750971793464
570 95601352305284234991764
571 100702444601272399657000
572 106071049779206203260107
573 111720956580076040002227
574 117666652332392813754757
575 123923357742101224569275
576 130507063385565283736709
577 137434567987667338846585
578 144723518570779723634449
579 152392452564590387773324
580 160460841970842639863975
581 168949139681665526682669
582 177878828054645238060317
583 187272469852834889731415
584 197153761662806247943092
585 207547589909364313401404
586 218480089590924905269262
587 229978705865586534972780
588 242072258623824577197431
589 254791010190328021423270
590 268166736303961824100803
591 282232800532042995593492
592 297024232282200262598555
593 312577808582961460682450
594 328932139811971366922310
595 346127759559347642529048
596 364207218822181083280632
597 383215184735589078667801
598 403198544055038537635941
599 424206511614928101960117
600 446290743998610875891156
601 469505458666263018828577
602 493907558798161018605972
603 519556764123192115404109
604 546515748014635314358740
605 574850281148644376700229
606 604629382034230287533173
607 635925474738170212267327
608 668814554142895632842889
609 703376359091390081032139
610 739694553789128156467081
611 777856917850536160193608
612 817955545394958141533289
613 860087053616164390828404
614 904352801268583030232878
615 950859117534238940690997
616 999717541755318375397944
617 1051045074539990281094622
618 1104964440772003924065702
619 1161604365079377050029668
620 1221099860342510467303868
621 1283592529849129963007302
622 1349230883730805795241589
623 1418170670345340558988448
624 1490575223299205363935281
625 1566615824836443715717904
626 1646472086353122454627445
627 1730332346831590812297544
628 1818394090024491018114871
629 1910864381256852729206121
630 2007960324753582483074092
631 2109909542441543671537778
632 2216950675217996471712905
633 2329333907722860931897554
634 2447321517698760285016357
635 2571188451072646477203607
636 2701222923943577624884204
637 2837727052715585004469241
638 2981017513669993933672901
639 3131426233330858558794688
640 3289301111037675551717462
641 3455006775204205502279202
642 3628925374808270428033245
643 3811457407727906788472129
644 4003022587611324258608994
645 4204060751045000005999379
646 4415032806862880590538817
647 4636421729523478618695264
648 4868733598567453168399911
649 5112498686259630182553914
650 5368272595613019978636600
651 5636637451091979206709069
652 5918203144393760212637625
653 6213608637816233335934333
654 6523523327830914736503230
655 6848648471598720323492354
656 7189718679287287734518942
657 7547503475177604107503322
658 7922808930680067776595080
659 8316479372520553048449394
660 8729399169501379629438559
661 9162494601395093437324980
662 9616735813686297648326029
663 10093138862043449817169761
664 10592767850574022385603286
665 11116737168097976395627927
666 11666213826861378889905929
667 12242419908309730445209748
668 12846635120744207317187838
669 13480199473899363545786810
670 14144516075702709597497247
671 14841054056711074104946161
672 15571351627960363554717385
673 16337019278220651349182663
674 17139743116911815404734440
675 17981288369212909060793937
676 18863503030185209999124276
677 19788321685031485806858886
678 20757769502926303184675530
679 21773966412181579541385258
680 22839131464851625705360226
681 23955587399240412537547467
682 25125765409144030992255704
683 26352210129051446237529697
684 27637584844929703778391313
685 28984676940644275475721757
686 30396403590503970817563024
687 31875817708881755448743946
688 33426114168340341021802104
689 35050636298193956900575024
690 36752882675957391357245199
691 38536514224680086178919285
692 40405361629728559066714367
693 42363433089175094916752413
694 44414922412565921323101979
695 46564217483488866705436984
696 48815909102029866772616086
697 51174800223911083050551116
698 53645915613831533499990897
699 56234511931296029564492923
700 58946088268010192672663835
701 61786397156751009317479586
702 64761456072483709573724460
703 67877559447399976124793014
704 71141291222489134989067741
705 74559537959236968676993238
706 78139502536065232030736502
707 81888718455193465881024528
708 85815064786711964065811547
709 89926781777816118354143336
710 94232487156356066010768453
711 98741193159117735491364283
712 103462324316559787491474733
713 108405736027102538252948119
714 113581733955487013983161074
715 119001094291212636209589363
716 124675084904607472699776563
717 130615487439704229181181194
718 136834620384774493935974548
719 143345363163132856168649820
720 150161181288647171948268181
721 157296152632302127803137309
722 164764994848145592178315865
723 172583094009022785368505136
724 180766534504656733361324786
725 189332130256887651056176687
726 198297457309222959837156629
727 207680887850297607478063499
728 217501625733384786646395557
729 227779743556755302364933379
730 238536221372442694035304932
731 249792987093857338703240528
732 261572958675688525590768817
733 273900088142666836087705344
734 286799407547011854717938583
735 300297076937791662468979964
736 314420434428951868100210539
737 329198048456464031961336411
738 344659772318876741241246262
739 360836801099559833507610295
740 377761731073093205866642420
741 395468621702600518861943109
742 413993060339344124716243890
743 433372229740616743289305463
744 453644978526866334646843968
745 474851894704111193337168369
746 497035382383020410858024960
747 520239741831590438489849536
748 544511253004118757506493753
749 569898262695202660182513384
750 596451275473751415626515032
751 624223048558537902586065817
752 653268690803607017862301327
753 683645765968949434230172311
754 715414400459215795175923302
755 748637395720937307714708602
756 783380345496708471308139724
757 819711758143128105370572697
758 857703184227959793421663937
759 897429349631016876909235327
760 938968294382673439380690085
761 982401517483708794950842693
762 1027814127960381431063728268
763 1075295002419259740344727081
764 1124936949377383189978112568
765 1176836880654852699236512914
766 1231095990128924310076485794
767 1287819940161173108744581596
768 1347119056022275602271208716
769 1409108528652499428359925882
770 1473908626110059659011847916
771 1541644914074176009163961453
772 1612448485784914761003861681
773 1686456201817802262427223852
774 1763810940107722779421675613
775 1844661856653845758393811321
776 1929164657355235109870530132
777 2017481881445464083455440030
778 2109783197013962246682565469
779 2206245709122049052945235136
780 2307054281042629792861479245
781 2412401869174442629770829084
782 2522489872204518035494776146
783 2637528495116248057313775862
784 2757737128665130464478039044
785 2883344744969961599160138120
786 3014590309893969686691047749
787 3151723212918223320836582920
788 3295003715238585930576570778
789 3444703416847638734162017547
790 3601105743394330320863394931
791 3764506453646760057574017440
792 3935214168417433691432619019
793 4113550921845679734809592722
794 4299852735968653697266420658
795 4494470219550628791783581541
796 4697769192180046309875786579
797 4910131334685229643397073157
798 5131954866962723741816410451
799 5363655254357068754101968242
800 5605665943777424633892098652
801 5858439130785004175416437064
802 6122446558935718557391098448
803 6398180352714973658745718602
804 6686153885456152038913502327
805 6986902683691166900482977945
806 7300985369440557332851920650
807 7628984642012112402133469681
808 7971508300940944173294346333
809 8329190311770492357135394453
810 8702691916443117493798277874
811 9092702790140954118795321362
812 9499942246492534677874761835
813 9925160493138601462017916186
814 10369139939731485356178056716
815 10832696560526703712744108872
816 11316681313813006829331497003
817 11821981620518255824408469970
818 12349522904423240151060828292
819 12900270196514129584320553852
820 13475229806106704129270873280
821 14075451061482122538746587338
822 14702028122884782354522467759
823 15356101870848116948868685957
824 16038861872933980446200491110
825 16751548432095934969305362096
826 17495454720006295748254216817
827 18271928998821574855747519963
828 19082376935001020708449383271
829 19928264008938667281075243373
830 20811118024320719747638502145
831 21732531721277625449838469382
832 22694165497563855664960206713
833 23697750242168693843497803658
834 24745090285938245234825798067
835 25838066473972917845965683270
836 26978639364755842473175851964
837 28168852561166596159029697286
838 29410836178741248610055208494
839 30706810456754692197277335273
840 32059089517924536973749091000
841 33470085282768113391536493298
842 34942311544885436396253936781
843 36478388213691941652291810449
844 38081045731385534143815755843
845 39753129671203625661301143208
846 41497605524307525757618209410
847 43317563682924465584160120781
848 45216224627681841150372818339
849 47196944327384680267547422429
850 49263219859816053773232605259
851 51418695262481931145765390367
852 53667167622577035954439376674
853 56012593415817401734020900511
854 58459095104168803394561357000
855 61010968002898909958725441326
856 63672687427795140254604379862
857 66448916133820727370843501220
858 69344512056928711332085709426
859 72364536371218466030969966707
860 75514261874102262159008205688
861 78799181712651320570454199830
862 82225018464812194630818916817
863 85797733589726252340227666191
864 89523537261947925494396080162
865 93408898604942444122057184219
866 97460556339851441421081210134
867 101685529866146366330004196216
868 106091130791445588619158535312
869 110684974928452777989483270928
870 115474994777682148766036391363
871 120469452515371928310009262606
872 125676953506751553315972293821
873 131106460365622162813589730602
874 136767307582034626509356572359
875 142669216740706264038643205295
876 148822312353707330260477999064
877 155237138331873015875949419768
878 161924675120356971759674871140
879 168896357524740079096910661482
880 176164093255144267320470159039
881 183740282216877623475265451615
882 191637836577254839716315341229
883 199870201639398340396477345703
884 208451377555031311870964165479
885 217395941909526601091343270292
886 226719073213776252062333157787
887 236436575338797740882585619824
888 246564902930396061331981173092
889 257121187842658297450231111472
890 268123266630570629703106543224
891 279589709143619627456229796245
892 291539848263871746509197635493
893 303993810833720135778680650317
894 316972549820247868121835869333
895 330497877764984708552925796324
896 344592501569732378981754277968
897 359280058671104350552156224180
898 374585154658472519479535956905
899 390533402392138310402931621660
900 407151462680752009550118867817
901 424467086579295317225776203103
902 442509159371320626799439900193
903 461307746301610510146704957751
904 480894140127984929250851619633
905 501300910563646209769849869130
906 522561955684215643922957975166
907 544712555376485451276880094856
908 567789426908888801463934142509
909 591830782706783733226839296579
910 616876390418857439021483186609
911 642967635364290914015460748467
912 670147585453784028353225304185
913 698461058681133436714803640708
914 727954693285784333912774162643
915 758677020690648065226416344520
916 790678541323495282972370869347
917 824011803434405301598887093266
918 858731485026081179398718168875
919 894894479018333900873978251151
920 932559981772702874557764994791
921 971789585108021344480950464926
922 1012647371942759682195474609160
923 1055200015705194955824652560587
924 1099516883657867556414613995204
925 1145670144288403640654534173137
926 1193734878924612102028681061962
927 1243789197737815955885446916774
928 1295914360304657320505673892375
929 1350194900904132490847299857917
930 1406718758733376401096961294994
931 1465577413232734646065021623160
932 1526866024717944254416109461658
933 1590683580524802912587390783373
934 1657133046879549056197084840337
935 1726321526716314306941087325242
936 1798360423671454571552427459857
937 1873365612493329720609558545096
938 1951457616115194322035437855846
939 2032761789648297317253977754588
940 2117408511562077807561419625066
941 2205533382328502144754248544558
942 2297277430818126183461859678245
943 2392787328746401783446188236728
944 2492215613480091285095776596555
945 2595720919525424775861096144568
946 2703468219031846374919805753087
947 2815629071657865748458640927432
948 2932381884158674580154646033629
949 3053912180068824312293976122864
950 3180412879867407273162749913190
951 3312084592027859250511986471990
952 3449135915369725058003526554089
953 3591783753145522087898797816455
954 3740253639312219011829980146423
955 3894780077453841685886932485094
956 4055606892839346166206626331902
957 4222987598118185250777755337083
958 4397185773174961939044344162186
959 4578475459684238168746343533154
960 4767141570926973651428914916964
961 4963480317451237061232847098687
962 5167799649181785560510021616871
963 5380419714605880237984084921941
964 5601673337686321773822954870313
965 5831906513177186337980297651673
966 6071478921043145761600032059783
967 6320764460709604601881766950809
968 6580151805898211498434304925704
969 6850044980830641969180495517726
970 7130863958612938596175564023496
971 7423045282643173934257372585031
972 7727042711916808128602133641240
973 8043327891136891627499513207296
974 8372391046570253018411697712213
975 8714741708626060533411868227417
976 9070909462169695670490219428109
977 9441444725622779677696221126666
978 9826919559939494088014190686094
979 10227928508590089715455944181232
980 10645089469724733740466635357196
981 11079044601734660247653110117875
982 11530461263473018773338286060161
983 12000032990444920753678263697957
984 12488480508325022181629676765665
985 12996552785211619414221801801552
986 13525028124078735163411776061004
987 14074715296942105153870266838800
988 14646454722311408595122597023839
989 15241119687559594499926414110945
990 15859617617900811792029830741435
991 16502891393731336559989665284041
992 17171920718153080848843638150642
993 17867723536566852370585617738062
994 18591357510292595277880899339670
995 19343921546246473287998612899000
996 20126557384779945902737954004758
997 20940451247864037566602764088214
998 21786835549882902839453826162024
999 22666990673384656545221656828533
1000 23582246812224367934887510293594