1 1
2 1
3 1
4 2
5 2
6 7
7 7
8 10
9 10
10 34
11 40
12 53
13 61
14 103
15 112
16 143
17 145
18 369
19 458
20 579
21 712
22 938
23 1127
24 1383
25 1638
26 2308
27 2754
28 3334
29 3925
30 5092
31 5818
32 6989
33 7759
34 12278
35 14819
36 17881
37 21477
38 25887
39 30929
40 36954
41 43943
42 52918
43 62749
44 74407
45 87854
46 104534
47 122706
48 144457
49 168661
50 203714
51 238919
52 280053
53 327371
54 384107
55 447180
56 520679
57 603914
58 711124
59 823628
60 954179
61 1101025
62 1283772
63 1472731
64 1698334
65 1936494
66 2323456
67 2679561
68 3087543
69 3554025
70 4087712
71 4696693
72 5392015
73 6184409
74 7088988
75 8117240
76 9287555
77 10617303
78 12130116
79 13844554
80 15790844
81 17994599
82 20505231
83 23336421
84 26540588
85 30162237
86 34258866
87 38879481
88 44095821
89 49975445
90 56625981
91 64095975
92 72509231
93 81969217
94 92636952
95 104585883
96 118027264
97 133078354
98 150196088
99 169225779
100 190563148
101 214470886
102 241257187
103 271232566
104 304776789
105 342284749
106 384259952
107 431116621
108 483453692
109 541864320
110 607098210
111 679772131
112 760821932
113 851065332
114 952017897
115 1064078915
116 1188809944
117 1327546236
118 1481943071
119 1653406521
120 1843956344
121 2055492691
122 2291058768
123 2551813953
124 2841154068
125 3161816632
126 3518174116
127 3911767143
128 4348308616
129 4830404734
130 5371315272
131 5964539248
132 6620830505
133 7346628872
134 8149040183
135 9035835052
136 10015580144
137 11097642456
138 12292340807
139 13610947847
140 15065875063
141 16670684088
142 18440289224
143 20390974565
144 22540643181
145 24908838553
146 27517050551
147 30388667882
148 33549413353
149 37027344960
150 40853227121
151 45060608198
152 49686263845
153 54770295364
154 60356656896
155 66493149329
156 73232194607
157 80630882849
158 88751713266
159 97662597483
160 107437985386
161 118158763275
162 129913900541
163 142798987738
164 156919463007
165 172389779775
166 189334806195
167 207890387334
168 228204683599
169 250438843195
170 274768584362
171 301384736512
172 330495401309
173 362326696055
174 397124943678
175 435157435686
176 476715496842
177 522115208603
178 571701540119
179 625846622048
180 684957194328
181 749474084101
182 819876646179
183 896684293239
184 980462093998
185 1071822463617
186 1171432168085
187 1280009993692
188 1398340172707
189 1527270978185
190 1667725306941
191 1820696906348
192 1987271314475
193 2168617369277
194 2366022733653
195 2580840196589
196 2814570963015
197 3068829837570
198 3345365950930
199 3646072366589
200 3972998931084
201 4328363494807
202 4714566820547
203 5134205156901
204 5590088120887
205 6085253531580
206 6622987445896
207 7206841182202
208 7840655505241
209 8528580057191
210 9275102444283
211 10085065623623
212 10963706812043
213 11916680580918
214 12950095401607
215 14070544650711
216 15285149675617
217 16601595486474
218 18028181468095
219 19573854063993
220 21248275863639
221 23061865930969
222 25025869565807
223 27152400537007
224 29454538800630
225 31946371166429
226 34643126060375
227 37561133058282
228 40718062840930
229 44132933573535
230 47826238697344
231 51820049741560
232 56138145525219
233 60806130195449
234 65851583873123
235 71304181320615
236 77195886372056
237 83561093440111
238 90436831280209
239 97862916926369
240 105882223654061
241 114540844707150
242 123888438882955
243 133978250956280
244 144867679913533
245 156618391556426
246 169296705614338
247 182973856299594
248 197726466350024
249 213636835934545
250 230793520810249
251 249291384059695
252 269232600589283
253 290726790143952
254 313891857088937
255 338853995813224
256 365749212316798
257 394723053665917
258 425933084409100
259 459545750448163
260 495741934760078
261 534715062907329
262 576672674946144
263 621837416507567
264 670448123057098
265 722760953685252
266 779050629560119
267 839611730362718
268 904760108310216
269 974834369934385
270 1050197489922925
271 1131238503922222
272 1218374349821805
273 1312051800777303
274 1412749565169354
275 1520980492842983
276 1637293969324883
277 1762278433036789
278 1896564103575200
279 2040825852542307
280 2195786311633364
281 2362219145255791
282 2540952590012930
283 2732873183481999
284 2938929793831251
285 3160137866985157
286 3397584011855701
287 3652430835808909
288 3925922161141262
289 4219388527976791
290 4534253126892694
291 4872038056455700
292 5234371069729096
293 5622992691909645
294 6039763882062747
295 6486674127013552
296 6965850144097527
297 7479565078346744
298 8030248384877504
299 8620496275333953
300 9253082936526994
301 9930972392075821
302 10657331232286695
303 11435542077297816
304 12269218018508569
305 13162217893812520
306 14118662665148933
307 15142952738595050
308 16239786535436447
309 17414180132491935
310 18671488299076076
311 20017426761528369
312 21458096035780027
313 23000006652865897
314 24650106149781914
315 26415807631469174
316 28305020337850275
317 30326181984600084
318 32488293347272350
319 34800954861052222
320 37274405765664301
321 39919565507527607
322 42748078035938312
323 45772358543545260
324 49005643635188723
325 52462044228746721
326 56156602112808753
327 60105349839535472
328 64325374608917942
329 68834885945746170
330 73653287861719267
331 78801255302404471
332 84300815635831903
333 90175434979894263
334 96450110191678472
335 103151466320686749
336 110307860423850980
337 117949491543623604
338 126108517833534211
339 134819180622777232
340 144117936527087400
341 154043597378265310
342 164637479164712468
343 175943559808325601
344 188008647049147252
345 200882556282440279
346 214618299741189147
347 229272286867022846
348 244904537449090950
349 261578907340658365
350 279363328475313544
351 298330063045980860
352 318555973766046844
353 340122810009517972
354 363117512047585717
355 387632532917980647
356 413766180931769498
357 441622981926736997
358 471314064266301628
359 502957566501805716
360 536679070304399665
361 572612058887551799
362 610898403747689797
363 651688879988818351
364 695143713446363128
365 741433159863110164
366 790738119632634103
367 843250788528973995
368 899175348349951005
369 958728697832646269
370 1022141228358956754
371 1089657644407622566
372 1161537834824797026
373 1238057794077182045
374 1319510599693919068
375 1406207446494375190
376 1498478743489917785
377 1596675274322984631
378 1701169427908704661
379 1812356499605255222
380 1930656072149139220
381 2056513475001089485
382 2190401332155329675
383 2332821198007021424
384 2484305293556302276
385 2645418339442776885
386 2816759503217910024
387 2998964447736386658
388 3192707518433434522
389 3398704041357996435
390 3617712763867473351
391 3850538434667167042
392 4098034535626201575
393 4361106170761628754
394 4640713124699361371
395 4937873096787667367
396 5253665124416188731
397 5589233202594093768
398 5945790114706826021
399 6324621482502197173
400 6727090051738158342
401 7154640222648961585
402 7608802843339354981
403 8091200276483417005
404 8603551759347082196
405 9147679068856496162
406 9725512513739924577
407 10339097267119752937
408 10990600063769635538
409 11682316277181832020
410 12416677403146996078
411 13196258966917047094
412 14023788883506264432
413 14902156290288977448
414 15834420884471410554
415 16823822787105681112
416 17873792969645311524
417 18987964267253545645
418 20170183018804885083
419 21424521360253539168
420 22755290216576879531
421 24167053021436121081
422 25664640213833520542
423 27253164546222033131
424 28938037257072215238
425 30724985147074079579
426 32620068617401843581
427 34629700713886798718
428 36760667241806361485
429 39020148000195316625
430 41415739207068803946
431 43955477170451007670
432 46647863284136993303
433 49501890409245767163
434 52527070729091463389
435 55733465144602732224
436 59131714309119286997
437 62733071375959193135
438 66549436566899188503
439 70593393646427917782
440 74878248419269559641
441 79418069346107857920
442 84227730407595282053
443 89322956321085210211
444 94720370257490818636
445 100437544171081758964
446 106493051904702247669
447 112906525198122361530
448 119698712781301482626
449 126891542688488952848
450 134508188001570826688
451 142573136155343209925
452 151112262071911022222
453 160152905244543229825
454 169723951046449652357
455 179855916453941490382
456 190581040442626765210
457 201933379285072745589
458 213948907032716291916
459 226665621435797791133
460 240123655613874860433
461 254365395758490313895
462 269435605212887885607
463 285381555241827768559
464 302253162872392087229
465 320103136152674523440
466 338987127249491878117
467 358963893768095767749
468 380095468763019935181
469 402447339861543703000
470 426088638015518195689
471 451092336354827664408
472 477535459707761462409
473 505499305313533540918
474 535069675351338826669
475 566337121865268728763
476 599397204781496546558
477 634350763652444851303
478 671304203895658065408
479 710369798234480754357
480 751666004192140998871
481 795317798409758621812
482 841457028742756540591
483 890222784951793870566
484 941761789114796371463
485 996228806608237866692
486 1053787078862186911057
487 1114608778935889613336
488 1178875491154930496278
489 1246778715999930742385
490 1318520401611733362311
491 1394313503223374075115
492 1474382572038753340396
493 1558964374992293451613
494 1648308547064024955112
495 1742678277743466013891
496 1842351033497254311434
497 1947619317977457516679
498 2058791472041811159739
499 2176192515437139977977
500 2300165032571102769555
501 2431070104303918618756
502 2569288288372803321985
503 2715220650763655378628
504 2869289850789515760157
505 3031941282442938296262
506 3203644275087612135420
507 3384893356227169975157
508 3576209579972384849895
509 3778141923992221864150
510 3991268758923804379932
511 4216199393435920621746
512 4453575699480175143602
513 4704073820842690561550
514 4968405970488126319263
515 5247322318923878792952
516 5541612982013113934597
517 5852110108921301658480
518 6179690078238084805952
519 6525275806549652784019
520 6889839175409542379504
521 7274403582551733367106
522 7680046623716094328457
523 8107902911527474115954
524 8559167038437716723862
525 9035096690829005894721
526 9537015921990240005154
527 10066318591787500073818
528 10624471981512074975675
529 11213020592521695033756
530 11833590138006300408218
531 12487891737367521787268
532 13177726323474524587732
533 13904989273245567294052
534 14671675272840783199707
535 15479883428970761003423
536 16331822638729701395499
537 17229817230617210556759
538 18176312890390861369498
539 19173882885687454353038
540 20225234604409151069613
541 21333216422211708242918
542 22500824915577355903349
543 23731212437346369614067
544 25027695072821278450100
545 26393760995005381747546
546 27833079238879849369303
547 29349508915133986342073
548 30947108885217475052724
549 32630147920163233978980
550 34403115367205050877624
551 36270732348871284997680
552 38237963520943177040946
553 40310029416409244259442
554 42492419404397720741528
555 44790905293907017746987
556 47211555614160397647122
557 49760750604354432102016
558 52445197947746313103119
559 55271949286085136667379
560 58248417552751866608215
561 61382395164161772828128
562 64682073111542943118310
563 68156060996536235647886
564 71813408056839595417138
565 75663625229609054132917
566 79716708303343129473023
567 83983162210640877905169
568 88474026517495814835525
569 93200902166643648944700
570 98175979536033969215236
571 103412067875563706798142
572 108922626189067386664581
573 114721795630860398172731
574 120824433490320555848517
575 127246148840551949785085
576 134003339931725131429921
577 141113233412529873801790
578 148593925468119890164847
579 156464424966082817382524
580 164744698707340387485936
581 173455718882380095931408
582 182619512839056823788815
583 192259215272078129264133
584 202399122950629095186959
585 213064752104884206504769
586 224282898599046830772487
587 236081701023305130421633
588 248490706844586260627426
589 261540941761240640954990
590 275264982414934172158066
591 289697032618827120877820
592 304873003269975363148199
593 320830596120295381630071
594 337609391590065169036647
595 355250940815002701509611
596 373798862128436851136566
597 393298942187883248535604
598 413799241966727830880875
599 435350207840317344075696
600 458004788008144302262166
601 481818554503286352437979
602 506849831053734857287568
603 533159827070679857890379
604 560812778053476525766508
605 589876092712502311492344
606 620420507127059697530136
607 652520246268116078502732
608 686253193233019782315997
609 721701066553229679260568
610 758949605954969708057145
611 798088766967999183909615
612 839212924798226407915067
613 882421087896683259311295
614 927817121679723717655491
615 975509982873756788536896
616 1025613964982134977870382
617 1078248955392079983503269
618 1133540704665979610518054
619 1191621108583631730132929
620 1252628503530795481275085
621 1316707975853817927977521
622 1384011685831426925004447
623 1454699206941558048032812
624 1528937881135168182788687
625 1606903190858354529744819
626 1688779148601189592739513
627 1774758704783877333103557
628 1865044174831202632444888
629 1959847686321528880783415
630 2059391647140527161420615
631 2163909235608484422144696
632 2273644913597837128754544
633 2388854963699932047191662
634 2509808051552031473864807
635 2636785814481962382783619
636 2770083477684417707741937
637 2910010499193691172214374
638 3056891244979231694991562
639 3211065695545979203506916
640 3372890185488480991453211
641 3542738177508594216734242
642 3721001072479541451442861
643 3908089057205582486537862
644 4104431991606013700260502
645 4310480337124871461749268
646 4526706128254173780782154
647 4753603989138067267302657
648 4991692197319220371604112
649 5241513796775816318372980
650 5503637762499727150782807
651 5778660218961559002675004
652 6067205714919484304770677
653 6369928557132709814521489
654 6687514205661440170456498
655 7020680733548749460759573
656 7370180353811425541894971
657 7736801016790889025170812
658 8121368081058512887458481
659 8524746061205131300297798
660 8947840456000332814527969
661 9391599660555044582398637
662 9857016966290401429065288
663 10345132652677367511668068
664 10857036174895938644000383
665 11393868451739000273481419
666 11956824258286445509240877
667 12547154728067493578724839
668 13166169969647255457814559
669 13815241802783448901263120
670 14495806619536376971824986
671 15209368375944215416133124
672 15957501720133631215101813
673 16741855262985451824709347
674 17564154997755650261524348
675 18426207875324210437800832
676 19329905542049511416907880
677 20277228247502764875415024
678 21270248929688765098489417
679 22311137485682880549518564
680 23402165235974892349788478
681 24545709591163085082303461
682 25744258930034131516486176
683 27000417698448800319999433
684 28316911738879831313293772
685 29696593860867277787719241
686 31142449663120060179911531
687 32657603618448918799186930
688 34245325433219728535224044
689 35909036693513348756957591
690 37652317810725762567210751
691 39478915279883795689514467
692 41392749264546866760230120
693 43397921522754943004820635
694 45498723689129702929431722
695 47699645928878027447703813
696 50005385980149860343408979
697 52420858601901548788569890
698 54951205445179608013283616
699 57601805366500809954348088
700 60378285202834473805722291
701 63286531028521031498808230
702 66332699915362723046238870
703 69523232218023550223668672
704 72864864407855338382523169
705 76364642479247401988602050
706 80029935953661656569929270
707 83868452507581852366433990
708 87888253251761884162547271
709 92097768690318501284981325
710 96505815389469697860272718
711 101121613386982294854025238
712 105954804374756131273107549
713 111015470688345108062964210
714 116314155138696524406629373
715 121861881722882938587851278
716 127670177252209281682077225
717 133751093937700983962309125
718 140117232974725476972542524
719 146781769170263852551138049
720 153758476658245881225307841
721 161061755750279476998000554
722 168706660971164630055330253
723 176708930330666271725663839
724 185085015885255746679299283
725 193852115645795752648645061
726 203028206889569985929215859
727 212632080937520071649719580
728 222683379460186024046271033
729 233202632378520642258697865
730 244211297428606706173054605
731 255731801462210864791259701
732 267787583558210322309763141
733 280403140023083869429919324
734 293604071362025283696079022
735 307417131305664214659049131
736 321870277981032616878340133
737 336992727319136457572918359
738 352815008795455956998997924
739 369369023603738655489022619
740 386688105367749940817998191
741 404807083500032849980645419
742 423762349321394151382057569
743 443591925059596732675273038
744 464335535850798482023525544
745 486034684872448269099971736
746 508732731741838106539860931
747 532474974320122370377223983
748 557308734067567632584169166
749 583283445101886808167530755
750 610450747117966911896804513
751 638864582333908373770622784
752 668581296635294267500233836
753 699659745096778266493228131
754 732161402067670818426921582
755 766150476015982122888490077
756 801694029333610856126300007
757 838862103313805787971881133
758 877727848520950316569308066
759 918367660781873182308265751
760 960861323037560788714069304
761 1005292153304074150930225960
762 1051747159001957673029719703
763 1100317197924192799563931385
764 1151097146124113675039119808
765 1204186073016374936320171072
766 1259687423996378318391752414
767 1317709210896221355739090080
768 1378364210608578815834958577
769 1441770172223647807579915885
770 1508050033038752490738180654
771 1577332143815074048889336878
772 1649750503671651735806210678
773 1725445005022910006139990252
774 1804561688982956164492420362
775 1887253011677361609827773804
776 1973678121921532286406377136
777 2064003150743712843866108196
778 2158401513250589964730311917
779 2257054223353982965847544853
780 2360150221898687182161632238
781 2467886718753771981896478790
782 2580469549453004933589726558
783 2698113546994164480166367765
784 2821042929432312216455667734
785 2949491703928193388254527348
786 3083704087940340693020667351
787 3223934948277725160267440494
788 3370450258759473520420822653
789 3523527577258789108153301340
790 3683456542940343404354695992
791 3850539394533563994326636571
792 4025091510519029370396265209
793 4207441972141088280692114830
794 4397934150197476827896982634
795 4596926316595586652793919754
796 4804792281705797515012228095
797 5021922058584382849244983162
798 5248722555182613689417278958
799 5485618295704258476935766322
800 5733052172321422504278654059
801 5991486228508002426503243889
802 6261402475301701333076315183
803 6543303741858946450896896930
804 6837714561722963378442511473
805 7145182096283051986686132085
806 7466277096963606051197027280
807 7801594907743960700915446011
808 8151756509675604512472141919
809 8517409609130970421487871485
810 8899229771588828461936363530
811 9297921602834531195784159854
812 9714219979529959777762104969
813 10148891331187245215380221704
814 10602734975663191221089376427
815 11076584510377034355122706608
816 11571309261543787319692293927
817 12087815793808125625024629499
818 12627049482760689877994635837
819 13189996152918959195844652302
820 13777683783859651786374889090
821 14391184287298069418770312629
822 15031615358023124634325657268
823 15700142401714084440840332151
824 16397980542787591098191515382
825 17126396715550358416252089741
826 17886711842065410770497879067
827 18680303100276877490449246296
828 19508606286081561358700824938
829 20373118273183778130773965665
830 21275399574724765447835876355
831 22217077010838260627884444017
832 23199846486451169338318257810
833 24225475883821531484727922314
834 25295808074486832813092657817
835 26412764055483014097161980473
836 27578346214889968804212005662
837 28794641731961759722309428943
838 30063826117310982372052921648
839 31388166898835484452072776886
840 32770027459303858556250135304
841 34211871031752548278604512293
842 35716264859093977687580204551
843 37285884524590579748727176842
844 38923518460115987806647346678
845 40632072639400673751793756004
846 42414575463747094336912356643
847 44274182847997609941773707686
848 46214183514849300593457996228
849 48238004505931946888250352584
850 50349216918401212177414261947
851 52551541876147039010116127531
852 54848856745079917638992165639
853 57245201602333536236442934165
854 59744785969613964515002388193
855 62351995821331449987392349888
856 65071400878573831541999344531
857 67907762200418949873168511971
858 70866040084540107091624601272
859 73951402289532005955184267672
860 77169232591877674586947317805
861 80525139690988018273387176085
862 84024966476277979228561367153
863 87674799670795146667083924995
864 91480979866491345637850251215
865 95450111966823518194885480138
866 99589076052990565170418223961
867 103905038690755971018947426664
868 108405464695475636367134067227
869 113098129373644577850062296255
870 117991131259998859169744217015
871 123092905369958432774928312404
872 128412236987976529866851464803
873 133958276013169939664162310196
874 139740551884446204477183927352
875 145768989108216487057939805555
876 152053923412691097164047704979
877 158606118553696417421109627756
878 165436783797931931925705285745
879 172557592110602218615911674656
880 179980699075416049532436042712
881 187718762576041099602012240408
882 195784963269243383576654613865
883 204193025881123335504240244229
884 212957241359090878223297832557
885 222092489913497780829752766906
886 231614264984172822802893140073
887 241538698168481624492955439993
888 251882585148964518713920877122
889 262663412660090356068605649175
890 273899386535208029540674822969
891 285609460876378579826348175187
892 297813368391435715060243316227
893 310531651944349233642121820989
894 323785697366761254311124013203
895 337597767580427105226180010362
896 351991038082228660426384775562
897 366989633845435601085809441043
898 382618667692977386826244415983
899 398904280200653395819220963468
900 415873681190459054784064033782
901 433555192876539531087145369397
902 451978294728708525213955892861
903 471173670120985588371916580271
904 491173254835220446432660764208
905 512010287492584845146148867988
906 533719361988531136324260941727
907 556336482009740068071130628552
908 579899117714618242278645264116
909 604446264662056374189317746115
910 630018505076433611629842882895
911 656658071540248718775718604961
912 684408913209287275548867680005
913 713316764648893234120071488919
914 743429217393715213042707182109
915 774795794337240928934279413987
916 807468027061529837514987096307
917 841499536221802614335889870188
918 876946115104959930392764615747
919 913865816485680423484257583102
920 952319042908502961908367022336
921 992368640529229737336255702804
922 1034079996654109332429615428194
923 1077521141120571341393108419236
924 1122762851668802145070168246831
925 1169878763459173895722695319288
926 1218945482896482311371147063811
927 1270042705928112564192660557712
928 1323253340989653981253583172046
929 1378663636778122744568509536626
930 1436363315039845896898821457121
931 1496445708567209282035504745979
932 1559007904605896258840410849738
933 1624150893881942976242136538695
934 1691979725465930503402063616012
935 1762603667699924360125897635941
936 1836136375421380008662414266588
937 1912696063727159213933113662615
938 1992405688530070149964118794300
939 2075393134169954709477126112563
940 2161791408351324312318027620559
941 2251738844689892053406507453364
942 2345379313161090374419234682374
943 2442862438754801545532935354529
944 2544343828652090726732211220179
945 2649985308251720770185529060687
946 2759955166386673475394509854817
947 2874428410083806869890640109208
948 2993587029233173241143009910956
949 3117620271547411926936177380290
950 3246724928206047105906613121138
951 3381105630594468611941568651127
952 3520975158562887897513398195442
953 3666554760646647127784545614350
954 3818074486705953843225908335299
955 3975773533460423034708236081947
956 4139900603411771887609551935707
957 4310714277666637214192547543649
958 4488483403190813122940762000358
959 4673487495046245203691873637222
960 4866017154182911353967878862477
961 5066374501379277963123024261739
962 5274873627947390097985078501881
963 5491841063841846500450748569934
964 5717616263835974099252346508278
965 5952552112453464578847639600674
966 6197015448369619941837809681598
967 6451387609023188709961539976205
968 6716064996207615136983808172414
969 6991459663439386169414384942430
970 7277999925931103886199086570837
971 7576130994027952290686635227993
972 7886315630998429231222963232643
973 8209034836103596418015579082378
974 8544788553903729460707166976382
975 8894096410797147287886995278346
976 9257498479823236816224288539904
977 9635556074800288403605777277005
978 10028852574908795418807547472562
979 10437994280872373856641703141367
980 10863611303931504965541113237326
981 11306358488849924787280768419487
982 11766916372239763961732845513280
983 12245992177539511607697048499580
984 12744320848028628464039901197482
985 13262666119314202550853145438328
986 13801821632778520930941998766080
987 14362612091531863066845390495284
988 14945894460472306340740757031601
989 15552559212113915719283604591540
990 16183531619906475296311468811139
991 16839773100833956877505401587701
992 17522282609145324706175677196382
993 18232098083140097715292911837699
994 18970297947002453464626311417622
995 19738002669751617842028272755700
996 20536376383452971700664514378917
997 21366628562913781584385109102889
998 22230015769169865076688302952083
999 23127843459154899464605566725306