1 1
2 1
3 3
4 2
5 6
6 6
7 11
8 11
9 22
10 23
11 37
12 42
13 65
14 76
15 111
16 127
17 182
18 217
19 294
20 351
21 471
22 562
23 734
24 881
25 1137
26 1364
27 1733
28 2074
29 2608
30 3127
31 3883
32 4644
33 5732
34 6838
35 8367
36 9963
37 12113
38 14395
39 17396
40 20614
41 24785
42 29314
43 35059
44 41360
45 49270
46 57979
47 68775
48 80753
49 95445
50 111810
51 131693
52 153914
53 180718
54 210770
55 246719
56 287122
57 335191
58 389272
59 453232
60 525319
61 610132
62 705803
63 817849
64 944284
65 1091795
66 1258317
67 1451797
68 1670268
69 1923292
70 2208930
71 2538680
72 2910914
73 3339390
74 3822903
75 4377988
76 5004075
77 5721125
78 6529521
79 7453146
80 8493878
81 9680508
82 11016676
83 12537086
84 14248046
85 16191263
86 18376479
87 20853965
88 23637923
89 26789062
90 30327410
91 34325992
92 38812557
93 43875270
94 49551332
95 55947186
96 63112427
97 71175400
98 80201243
99 90344860
100 101690859
101 114426385
102 128660475
103 144618752
104 162441000
105 182399674
106 204672149
107 229587358
108 257369827
109 288416238
110 323009174
111 361627183
112 404624169
113 452577519
114 505928790
115 565373716
116 631461649
117 705031226
118 786762726
119 877666536
120 978583399
121 1090729599
122 1215140969
123 1353281282
124 1506423126
125 1676327477
126 1864554159
127 2073219534
128 2304231710
129 2560133488
130 2843252695
131 3156642514
132 3503138343
133 3886403125
134 4309883450
135 4777971454
136 5294848606
137 5865778210
138 6495824864
139 7191290008
140 7958298573
141 8804390726
142 9736960243
143 10765022942
144 11897492470
145 13145140209
146 14518696044
147 16031020007
148 17695009704
149 19526007870
150 21539497460
151 23753767563
152 26187381714
153 28862126413
154 31800228384
155 35027620603
156 38570886022
157 42460868431
158 46729322982
159 51412907494
160 56549511630
161 62182670965
162 68357545621
163 75125797669
164 82541196530
165 90665003764
166 99561169278
167 109302283241
168 119964329560
169 131633255590
170 144399253727
171 158364012318
172 173634484485
173 190330894596
174 208579952759
175 228523690340
176 250312087734
177 274112819614
178 300103246113
179 328481171618
180 359456154004
181 393261371146
182 430144209606
183 470379353169
184 514258597314
185 562105292826
186 614263333001
187 671113087122
188 733059521930
189 800549773518
190 874060343126
191 954116492299
192 1041278460874
193 1136162862682
194 1239427886146
195 1351796900615
196 1474042582913
197 1607012976418
198 1751614492379
199 1908840673031
200 2079754040817
201 2265517844830
202 2467376707236
203 2686691690503
204 2924919707540
205 3183652248009
206 3464593543631
207 3769603347615
208 4100673832180
209 4459976872716
210 4849839672465
211 5272797030510
212 5731565732893
213 6229102339198
214 6768576361346
215 7353434201444
216 7987371178234
217 8674402272878
218 9418833115259
219 10225338293984
220 11098931416499
221 12045051846307
222 13069533999222
223 14178703439905
224 15379345663124
225 16678812594357
226 18084991113328
227 19606421174986
228 21252264421231
229 23032435218254
230 24957569814951
231 27039171779018
232 29289582209602
233 31722141259025
234 34351160027148
235 37192100015295
236 40261547508322
237 43577413035233
238 47158909128559
239 51026772181390
240 55203244673146
241 59712322019823
242 64579740597719
243 69833252542836
244 75502621075968
245 81619926606301
246 88219571142331
247 95338619409213
248 103016814503802
249 111296958200791
250 120224940278770
251 129850162790226
252 140225585926801
253 151408201510682
254 163459098791232
255 176443993123476
256 190433315544443
257 205502803397400
258 221733618169190
259 239213005583624
260 258034446970090
261 278298397302449
262 300112476058503
263 323592292850969
264 348861684697826
265 376053639958879
266 405310590057592
267 436785443850702
268 470641942929504
269 507055820139674
270 546215228973740
271 588322041578862
272 633592364409000
273 682257993006127
274 734567027690553
275 790785504717173
276 851198127837288
277 916110097712987
278 985847977552050
279 1060761745507270
280 1141225815023573
281 1227641338151406
282 1320437404200528
283 1420073625274275
284 1527041540281288
285 1641867517962982
286 1765114396876319
287 1897384745803966
288 2039322774644525
289 2191617996870572
290 2355007451202797
291 2530279816506495
292 2718277989386654
293 2919903708358372
294 3136120538697212
295 3367959069668335
296 3616520365105637
297 3882981805514567
298 4168601070460771
299 4474722706584250
300 4802782716840518
301 5154315945292464
302 5530961358422399
303 5934470349065150
304 6366712806061846
305 6829686452626958
306 7325523813403384
307 7856502716685560
308 8425054282522106
309 9033774734371670
310 9685434547746498
311 10382991735264454
312 11129602313648767
313 11928635246094138
314 12783684406148108
315 13698585384279761
316 14677429149923745
317 15724580954936479
318 16844695921103920
319 18042740301597644
320 19324009250724940
321 20694150736759599
322 22159185783095373
323 23725535362313622
324 25400043434898865
325 27190007194438266
326 29103203271728627
327 31147921746603304
328 33332995931343526
329 35667840615764808
330 38162485896121197
331 40827620176710649
332 43674628569397144
333 46715641238914104
334 49963576963287818
335 53432197481986781
336 57136156881376658
337 61091062684329335
338 65313531807777481
339 69821259222269068
340 74633081320732202
341 79769053077092905
342 85250519769184268
343 91100203677277645
344 97342285220706374
345 104002500362778882
346 111108232350076353
347 118688621131177874
348 126774667033415396
349 135399353659043060
350 144597764997616070
351 154407223439006627
352 164867422001195371
353 176020579296053250
354 187911588756367264
355 200588192608771164
356 214101150212403613
357 228504433338224008
358 243855415985676639
359 260215093541678558
360 277648296726732738
361 296223937511097919
362 316015250160533308
363 337100067128224928
364 359561090524875048
365 383486201585719938
366 408968766286707281
367 436107982409370993
368 465009223468612923
369 495784427871607992
370 528552485816052038
371 563439675568000276
372 600580098541474336
373 640116168307472957
374 682199099681950683
375 726989456734832825
376 774657702398611272
377 825384812478164778
378 879362893057673342
379 936795868325872612
380 997900173912909682
381 1062905527253662890
382 1132055705935339260
383 1205609410333758886
384 1283841137111978360
385 1367042144988892337
386 1455521434709723724
387 1549606830060474546
388 1649646076943431217
389 1756008053147242946
390 1869084000623493689
391 1989288879073713286
392 2117062747152263458
393 2252872276659561795
394 2397212300206508674
395 2550607504726503787
396 2713614165152864248
397 2886822038097723390
398 3070856303337146537
399 3266379680882356027
400 3474094604558946156
401 3694745588339046209
402 3929121659073716790
403 4178059000889497742
404 4442443677216216242
405 4723214585314786569
406 5021366501165296309
407 5337953379819937007
408 5674091760522232161
409 6030964452603383678
410 6409824342432159055
411 6811998509045725530
412 7238892479222418363
413 7691994822004719080
414 8172881903400803366
415 8683223014466975358
416 9224785682933223508
417 9799441395630119907
418 10409171530754596084
419 11056073742216455226
420 11742368583389769725
421 12470406628481866649
422 13242675866526238348
423 14061809643230985181
424 14930594912739059166
425 15851981092678247732
426 16829089270944231947
427 17865222076942365685
428 18963873951438825421
429 20128742148370648044
430 21363738187765571454
431 22673000115118584605
432 24060905270636489716
433 25532083947158968451
434 27091433623673746870
435 28744134178253862008
436 30495663750058483807
437 32351815680921036351
438 34318716188076605206
439 36402843227037491570
440 38611046177253440695
441 40950566839955917454
442 43429061361056972769
443 46054623600943998299
444 48835809543394415044
445 51781663300084768484
446 54901744281385831684
447 58206156126888507494
448 61705576943912486592
449 65411291486928914797
450 69335224802779488709
451 73489978016801130722
452 77888865760441286365
453 82545955960524247384
454 87476111465517805606
455 92695034277107622500
456 98219311836239815684
457 104066466183400171438
458 110255005415167053974
459 116804478311811163814
460 123735531529923127292
461 131069970293665561348
462 138830821949645299831
463 147042403381919725142
464 155730391622256334708
465 164921898719458988287
466 174645550172138541824
467 184931568060766989700
468 195811858151812447422
469 207320102186890985728
470 219491854597385175633
471 232364644939999146252
472 245978085260642549418
473 260373983770513023625
474 275596464008067051148
475 291692090965451540081
476 308710003318852979457
477 326702053342804290767
478 345722953613250187169
479 365830432188184131798
480 387085395335693959997
481 409552099614859224752
482 433298332344246738626
483 458395602388522864672
484 484919340262884344996
485 512949109620026334736
486 542568829084543915108
487 573867006643512615634
488 606936985523844409565
489 641877203919766211892
490 678791467467494297514
491 717789236996487820663
492 758985930421903845093
493 802503241485999887079
494 848469474182119315662
495 897019895760651372650
496 948297107121477674615
497 1002451433698314382891
498 1059641335612646069156
499 1120033840424189343243
500 1183804997231629656631
501 1251140355688830801786
502 1322235468669755338188
503 1397296422403675667239
504 1476540392797495934076
505 1560196232042718751583
506 1648505084212332318239
507 1741721034242246922842
508 1840111788996712024638
509 1943959395132343525806
510 2053560992460963127239
511 2169229607870651908771
512 2291294988513694689750
513 2420104479692370280892
514 2556023946168607147548
515 2699438742729050155698
516 2850754732759046251042
517 3010399361089115339766
518 3178822779906553274782
519 3356499034461767795624
520 3543927307414392540807
521 3741633229051715724597
522 3950170252291900506533
523 4170121100247447496364
524 4402099285345893896211
525 4646750708369414610254
526 4904755336514136917062
527 5176828969464055347297
528 5463725092705904004583
529 5766236827764057165710
530 6085198978731881472052
531 6421490185518041446817
532 6776035183361778076810
533 7149807179835096319157
534 7543830349094321204416
535 7959182455463495060426
536 8396997606355121176262
537 8858469147545886764471
538 9344852701094602083321
539 9857469359931892931230
540 10397709039733774992783
541 10967034003203866816769
542 11566982557749482153349
543 12199172942862021209282
544 12865307408613718199806
545 13567176502865147241452
546 14306663569082089918475
547 15085749473746950273481
548 15906517565816356095151
549 16771158888716917236810
550 17681977647957657171244
551 18641396956484027718904
552 19651964861560798450656
553 20716360677078769219626
554 21837401625872284998790
555 23018049817861527020694
556 24261419569506956142366
557 25570785092470982745845
558 26949588557986091145532
559 28401448567081806293520
560 29930169034304997375912
561 31539748517534788415573
562 33234390002798277322819
563 35018511179345672966104
564 36896755215313459331482
565 38874002072118251607274
566 40955380369498899836991
567 43146279842480123963686
568 45452364403947961041214
569 47879585857509280984766
570 50434198276301039434271
571 53122773096112442703194
572 55952214940684637543210
573 58929778231559609982095
574 62063084602788178660790
575 65360141177222996917497
576 68829359727422958759498
577 72479576782625347426642
578 76320074707827385352340
579 80360603821573285986858
580 84611405581832457968022
581 89083236912150366733962
582 93787395701163216374183
583 98735747553728374040082
584 103940753830864860856362
585 109415501063354075526400
586 115173731780735268012036
587 121229876847718867053547
588 127599089354772443666186
589 134297280162700885534552
590 141341155153523260515539
591 148748254295947254685442
592 156536992583870391454009
593 164726702965429545020304
594 173337681327790105475690
595 182391233665223901101504
596 191909725503126736324787
597 201916633716430612000555
598 212436600823285836843820
599 223495491904330463005965
600 235120454237485152674762
601 247339979811494402185141
602 260183970818134533977427
603 273683808300346170503756
604 287872424067201399531142
605 302784376068234070592575
606 318455927350136895462369
607 334925128804967765298594
608 352231905846171437641623
609 370418149239635121507386
610 389527810240710403023653
611 409607000284088063494532
612 430704095393533558719850
613 452869845579770590509654
614 476157489411181980647614
615 500622874048902326661185
616 526324580950368501393833
617 553324057558242911664292
618 581685755200070674407577
619 611477273543161113799190
620 642769511853426115332829
621 675636827432673847437800
622 710157201508731946467736
623 746412412985554790121363
624 784488220355812052915365
625 824474552218651281895764
626 866465706735967254449934
627 910560560508545428310174
628 956862787239211693126250
629 1005481086706444023236138
630 1056529424452615538029356
631 1110127282756127803271398
632 1166399923332178098956578
633 1225478662381265173313086
634 1287501158474613902297180
635 1352611713949868222163247
636 1420961590354886502149681
637 1492709338672020244137729
638 1568021144913967921621614
639 1647071191887824305925930
640 1730042037776699568556517
641 1817125012405434521583525
642 1908520631903551928382140
643 2004439032708041010792180
644 2105100425688863564135428
645 2210735571422555799461454
646 2321586277473089241619330
647 2437905918795437282694855
648 2559959982204403700934967
649 2688026636122167742636560
650 2822397326638257774642946
651 2963377401202047142890142
652 3111286761081103736109983
653 3266460544021513541882185
654 3429249838352355767641536
655 3600022430096685764123630
656 3779163584450106617393662
657 3967076863326623608038265
658 4164184980462726059773889
659 4370930695928801486916836
660 4587777751680632804104342
661 4815211850162621063287558
662 5053741677750302411594685
663 5303899975220611126331552
664 5566244657206449059967584
665 5841359983016339171892691
666 6129857780960152214469826
667 6432378728770877768000961
668 6749593692464668930576884
669 7082205126456660498471890
670 7430948537494335173309370
671 7796594015473395954651437
672 8179947833937392614225365
673 8581854123595179294410062
674 9003196621918617659850425
675 9444900502447261353569382
676 9907934287147213220392745
677 10393311845769130943644608
678 10902094485863043236111788
679 11435393137740988789970734
680 11994370638383568661675085
681 12580244118957662316500480
682 13194287500310243320766518
683 13837834101514595801463050
684 14512279366235800356613700
685 15219083712436487835928210
686 15959775510627651386910766
687 16735954196668933843802807
688 17549293524800241727535428
689 18401544967434581004053946
690 19294541267913586216165108
691 20230200153326796851604408
692 21210528214162047036692743
693 22237624958508790540642649
694 23313687048197927487954728
695 24441012725274595935307634
696 25622006436858376845239043
697 26859183667520514100840954
698 28155175987962912945267968
699 29512736329925170065371482
700 30934744496899301063036384
701 32424212921444024812326239
702 33984292679543353646001082
703 35618279773741810423606971
704 37329621696442355694088402
705 39121924286121061311403054
706 40998958888868783552364057
707 42964669839123780860997597
708 45023182273119677038612644
709 47178810290118340435965312
710 49436065476163954421257658
711 51799665806737347803163404
712 54274544944364864325382044
713 56865861948983054022437766
714 59579011418546710763015052
715 62419634079226053498466703
716 65393627844238944259843147
717 68507159362341143925542089
718 71766676076714704242109875
719 75178918817098649757257784
720 78750934947743704255416066
721 82490092096012518447544144
722 86404092486208851875532545
723 90500987905603840256997403
724 94789195329418188423440636
725 99277513234058792802124614
726 103975138627732499330242816
727 108891684830265092113124210
728 114037200033816592475573341
729 119422186679066586733282860
730 125057621681350911899734293
731 130954977544303286772417272
732 137126244398514160089134278
733 143583953005994205367703229
734 150341198771246757809744774
735 157411666803245802681597818
736 164809658072698999738302450
737 172550116712700009530401946
738 180648658511031881389557860
739 189121600646356956348746196
740 197985992720770315985670772
741 207259649145434076159928537
742 216961182936345881479209945
743 227110040981820775961047562
744 237726540843707566206496762
745 248831909159192555792077694
746 260448321710603862495689951
747 272598945235789145136625150
748 285307981052331998292948804
749 298600710574383291245136375
750 312503542801723263931572654
751 327044063866557928165250416
752 342251088724556388084890817
753 358154715082927357269015578
754 374786379659517708686003584
755 392178916873640742660075391
756 410366620070727542058359363
757 429385305390084278604613276
758 449272378386646593555959379
759 470066903525310144475783480
760 491809676668270666276820652
761 514543300684029720949166898
762 538312264308848122122795855
763 563163024400225839187211237
764 589144091724412435142308852
765 616306120429364996045314866
766 644702001357325599328869368
767 674386959361264642036284592
768 705418654792554410192405170
769 737857289338021635493876338
770 771765716388044912734443134
771 807209556128909724921136225
772 844257315556589326414352898
773 882980513621485521908843990
774 923453811718100045354664131
775 965755149746852642931171896
776 1009965887980226355712549114
777 1056170954979610828076721834
778 1104459001814757235500419679
779 1154922562852963986882079748
780 1207658223391288574319815179
781 1262766794421377401356125875
782 1320353494823374961119515529
783 1380528141302842529030236560
784 1443405346392244463144111256
785 1509104724857288998588422327
786 1577751108856867420521225264
787 1649474772225418662598819668
788 1724411664255909214195372885
789 1802703653383157335591284726
790 1884498781177582608509161465
791 1969951527082566283326536926
792 2059223084340039576463969126
793 2152481647573704565488672065
794 2249902712511901867925263422
795 2351669388358736602964987313
796 2457972723335968038737944090
797 2569012043946711940860103012
798 2684995308527298434166350682
799 2806139475684265050946739228
800 2932670888230283606590471066
801 3064825673265707869325371110
802 3202850159070908947300363258
803 3347001309509875468232210842
804 3497547176665843774459332788
805 3654767372467638774271488883
806 3818953560087661946359431985
807 3990409965933181195482870048
808 4169453913076973643583851221
809 4356416377017106114406433312
810 4551642564682362175191736850
811 4755492517646802770766124823
812 4968341740546202032376919718
813 5190581855739569122970316860
814 5422621285290971466047887648
815 5664885961401100650355121555
816 5917820066453014331657120585
817 6181886803894756023042510674
818 6457569201219791410685833896
819 6745370946368818945943506900
820 7045817258918272223427031182
821 7359455797488132890169389832
822 7686857604847256696119980817
823 8028618092266755701819524725
824 8385358064721713345071479924
825 8757724788619273108189944558
826 9146393103785377319343941302
827 9552066581526034291465848056
828 9975478730638110849936663974
829 10417394253334532387552672432
830 10878610353113186385287959095
831 11359958096695473845022525650
832 11862303832230607113928474658
833 12386550666065681362591156601
834 12933640000457922532765368736
835 13504553134717280148469368766
836 14100312932350650600230960181
837 14721985556899218094870418282
838 15370682279250821387170513686
839 16047561359338537174948793890
840 16753830005235002895535819694
841 17490746412791060262101000175
842 18259621889074199628509104891
843 19061823063011867599255722271
844 19898774186760874449479396802
845 20771959531485049187580825622
846 21682925881349504779008308020
847 22633285129712983154101493867
848 23624716981636831057226626490
849 24658971767015394004756287232
850 25737873368781455835352985081
851 26863322270840721367830801516
852 28037298730550901640449725372
853 29261866080776546651778102482
854 30539174166726093643781301508
855 31871462923009564130923578777
856 33261066096545548962634844927
857 34710415121195718906020401264
858 36222043150211397831711368728
859 37798589252845315912210438396
860 39442802781705359535747816601
861 41157547917716149206485893657
862 42945808399796784895692530194
863 44810692446674110092968062040
864 46755437878513683051409192816
865 48783417446385334952616681689
866 50898144377865000686175926244
867 53103278147434689118813509817
868 55402630480651002805435012330
869 57800171601440236727432604960
870 60300036732212272799257174945
871 62906532856902641905405425129
872 65624145757414012683970647346
873 68457547334377313246932961636
874 71411603223544496682686512835
875 74491380719608128388952881540
876 77702157019667085009919598641
877 81049427799077655117323730400
878 84538916132888326662470668046
879 88176581776616191251320670160
880 91968630820619549870816835735
881 95921525732923619426207494511
882 100041995805893545946912805614
883 104337048022797169421978555811
884 108813978360881168050552470716
885 113480383548281874703224914080
886 118344173292720591777512023594
887 123413583000684088540868418174
888 128697187006470592040462431736
889 134203912331289685847109193528
890 139943052993339283761771340494
891 145924284890652553236875427903
892 152157681279301885442856154971
893 158653728870483009946780120764
894 165423344570860721618577734386
895 172477892891565025327437984962
896 179829204052154059335502916741
897 187489592806944257689792705156
898 195471878022110378452921220886
899 203789403033124719570670115047
900 212456056813187463890168540537
901 221486295984555659665127610376
902 230895167705847705684048912449
903 240698333469751392179664212004
904 250912093846826426121049681996
905 261553414212546424421389107484
906 272639951496089040103556156734
907 284190081990947616285511176265
908 296222930268910094669298644956
909 308758399240634698844198631172
910 321817201407641339709404963505
911 335420891352349567351514515463
912 349591899514509504213143226446
913 364353567304321851993398944433
914 379730183604394638783411925128
915 395747022714782236190831698996
916 412430383797350237354539840340
917 429807631877967062721527217552
918 447907240467179031222636957781
919 466758835862454370257494713544
920 486393243197407499534124227273
921 506842534306028068717316176583
922 528140077472448185357080183738
923 550320589139592742077744210366
924 573420187652763898898254298845
925 597476449117235535974938559856
926 622528465451851990145779985494
927 648616904723879512075469991575
928 675784073853506035443800318441
929 704073983779885614551270916000
930 733532417184017232783084698018
931 764206998867513657354375085969
932 796147268889974408922654606189
933 829404758571728046294838218187
934 864033069472652681081889547712
935 900087955462141364202455286830
936 937627407999529820301628554786
937 976711744748991360910398284196
938 1017403701657485195445854599597
939 1059768528629386086834948721822
940 1103874088936360432914944889030
941 1149790962506476539479130576606
942 1197592553241856810406602660408
943 1247355200520011780119691646254
944 1299158295039727803856106650056
945 1353084399178652612960866963835
946 1409219372035898044447783443502
947 1467652499339724788736970974695
948 1528476628407025930198842470539
949 1591788308348580124555668332939
950 1657687935721210141058475751916
951 1726279905835783112788228113230
952 1797672769937705491679958132076
953 1871979398484953688641312846019
954 1949317150756991507287236690632
955 2029808051036944670748054042592
956 2113578971618351150773026833121
957 2200761822897503481958440927440
958 2291493750822034070353226721646
959 2385917341976820810381609780044
960 2484180836598663273980708407449
961 2586438349822389146045711348591
962 2692850101472217193686759731875
963 2803582654724253844259235631663
964 2918809163978020376880886462186
965 3038709632287862456916693699761
966 3163471178718031054909042925162
967 3293288315999149613603704217134
968 3428363238877705821674342453958
969 3568906123565175366572235864730
970 3715135438708368597151063058213
971 3867278268318680618813975491094
972 4025570647114048294863216757699
973 4190257908744710860878036315042
974 4361595047391218377352019200776
975 4539847093241718270157236595377
976 4725289502374213738833606642992
977 4918208561589462306550544177623
978 5118901808760260497215607321785
979 5327678469284326267251836809982
980 5544859909249588093727472600674
981 5770780105943756595685167216336
982 6005786136363284517982581336463
983 6250238684401607448540903332778
984 6504512567421541680383034968692
985 6768997282943348600205410909260
986 7044097576206843417042857044713
987 7330234029394541557117631029511
988 7627843673331728713251534703644
989 7937380622510084622808596369712
990 8259316734312557603812818698150
991 8594142293350216199612336963494
992 8942366721855206555329602919892
993 9304519317109426762841259329177
994 9681150016924439775139749117018
995 10072830194226262669255496353159
996 10480153481837273861948003444636
997 10903736628588422988742773405706
998 11344220387936424313775441359898
999 11802270440304591965562063611922
1000 12278578350410577124406099033772