5 1
6 4
7 11
8 29
9 76
10 199
11 518
12 1324
13 3278
14 7784
15 17643
16 38138
17 78753
18 155793
19 296248
20 543333
21 964239
22 1660748
23 2783499
24 4550843
25 7273394
26 11385571
27 17485634
28 26385946
29 39175444
30 57296576
31 82639259
32 117654736
33 165492559
34 230164301
35 316738004
36 431567803
37 582563629
38 779506388
39 1034414539
40 1361968553
41 1780000328
42 2310055263
43 2978035358
44 3814932408
45 4857661098
46 6150002584
47 7743669963
48 9699507894
49 12088839533
50 14994974889
51 18514895696
52 22761132929
53 27863854171
54 33973179164
55 41261743051
56 49927528039
57 60196985486
58 72328471739
59 86616022426
60 103393491334
61 123039081488
62 145980297584
63 172699350523
64 203739046444
65 239709194363
66 281293568293
67 329257461548
68 384455872823
69 447842365593
70 520478644388
71 603544893579
72 698350926453
73 806348194564
74 929142709623
75 1068508932534
76 1226404686596
77 1404987154374
78 1606630020296
79 1833941823659
80 2089785589426
81 2377299806969
82 2699920829761
83 3061406771944
84 3465862980701
85 3917769166439
86 4422008275948
87 4983897196939
88 5609219385683
89 6304259512874
90 7075840226323
91 7931361132658
92 8878840103858
93 9926957018188
94 11085100048928
95 12363414618203
96 13772855137224
97 15325239658343
98 17033307568509
99 18910780457988
100 20972426302579
101 23234127102021
102 25712950121844
103 28427222890571
104 31396612108929
105 34642206632576
106 38186604694799
107 42054005540686
108 46270305649424
109 50863199726626
110 55862286653944
111 61299180588683
112 67207627411694
113 73623626727493
114 80585559626329
115 88134322423808
116 96313466599673
117 105169345163443
118 114751265680828
119 125111650201163
120 136306202332543
121 148394081717894
122 161438086171883
123 175504841745354
124 190665000990878
125 206993449710024
126 224569522470096
127 243477227185339
128 263805479064996
129 285648344238099
130 309105293372501
131 334281465613404
132 361287943174511
133 390242036922929
134 421267583307076
135 454495252985099
136 490062871519693
137 528115752513724
138 568807043569703
139 612298085464934
140 658758784943068
141 708368001531838
142 761313948805928
143 817794610523243
144 878018172072298
145 942203467678033
146 1010580443823089
147 1083390639351448
148 1160887682731349
149 1243337806964543
150 1331020382639244
151 1424228469634571
152 1523269387994859
153 1628465308502946
154 1740153863492419
155 1858688778449826
156 1984440524969034
157 2117796995631236
158 2259164201395584
159 2408966992097051
160 2567649800659904
161 2735677411647103
162 2913535754778029
163 3101732724059188
164 3300799023184939
165 3511289037877853
166 3733781735851028
167 3968881595087563
168 4217219561145433
169 4479454034209208
170 4756271886623423
171 5048389511655934
172 5356553904253288
173 5681543774563994
174 6024170695019608
175 6385280281777739
176 6765753411345446
177 7166507473216029
178 7588497659366921
179 8032718291481264
180 8500204186770801
181 8992032063292939
182 9509321985670236
183 10053238852136139
184 10624993923846551
185 11225846397412734
186 11857105021627163
187 12520129759370234
188 13216333495702198
189 13947183793161344
190 14714204695306288
191 15518978579557243
192 16363148060408348
193 17248417944100523
194 18176557235861893
195 19149401200840588
196 20168853479872679
197 21236888261246153
198 22355552509640164
199 23526968253437323
200 24753334931625509
201 26036931801524596
202 27380120408592599
203 28785347119585046
204 30255145720360884
205 31792140079647926
206 33399046880100744
207 35078678418004011
208 36833945472994594
209 38667860249196201
210 40583539389181089
211 42584207062194248
212 44673198128096589
213 46853961378504983
214 49130062856628524
215 51505189257322123
216 53983151408900483
217 56567887838277658
218 59263468421019763
219 62074098117920978
220 65004120799735778
221 68058023161723324
222 71240438729683168
223 74556151959184859
224 78010102429717688
225 81607389135510679
226 85353274874797021
227 89253190739321444
228 93312740705913571
229 97537706331975029
230 101934051556753076
231 106507927610298699
232 111265678032032561
233 116213843800867824
234 121359168578864751
235 126708604070418094
236 132269315499004608
237 138048687203544594
238 144054328356458168
239 150294078805523979
240 156776015041675358
241 163508456294896373
242 170499970760407993
243 177759381957362528
244 185295775222292713
245 193118504339590243
246 201237198311317244
247 209661768268683083
248 218402414527548079
249 227469633790345078
250 236874226496839499
251 246627304326178346
252 256740297852708814
253 267224964358077496
254 278093395802151824
255 289358026955336251
256 301031643694886804
257 313127391467859011
258 325658783923355829
259 338639711716774076
260 352084451488779999
261 366007675021776993
262 380424458576661124
263 395350292412693003
264 410801090493347709
265 426793200381037868
266 443343413323638663
267 460468974535777478
268 478187593677885068
269 496517455536039598
270 515477230905669608
271 535086087682216939
272 555363702161895898
273 576330270555720449
274 598006520720006993
275 620413724106596344
276 643573707936074821
277 667508867597310959
278 692242179276661196
279 717797212820235019
280 744198144832647451
281 771469772015724434
282 799637524750664611
283 828727480927199234
284 858766380023330426
285 889781637439266804
286 921801359089214528
287 954854356254721179
288 988970160703309488
289 1024179040076177839
290 1060512013548784653
291 1098000867768174228
292 1136678173070942363
293 1176577299985781133
294 1217732436024583508
295 1260178602766130123
296 1303951673236422409
297 1349088389589768488
298 1395626381094770719
299 1443604182429406558
300 1493061252289437464
301 1544037992314423946
302 1596575766335668504
303 1650716919950452171
304 1706504800426974614
305 1763983776944452301
306 1823199261172874089
307 1884197728196958736
308 1947026737788904289
309 2011734956034565051
310 2078372177317737884
311 2146989346667285963
312 2217638582471874759
313 2290373199567141998
314 2365247732700170619
315 2442317960376181338
316 2521640929092409318
317 2603274977964177648
318 2687279763748228848
319 2773716286268424443
320 2862646914248971788
321 2954135411560386779
322 3048246963883450853
323 3145048205796470764
324 3244607248291200023
325 3346993706722831609
326 3452278729199522596
327 3560535025416962699
328 3671836895943550421
329 3786260261961792484
330 3903882695471594551
331 4024783449961163894
332 4149043491551297636
333 4276745530618883494
334 4407974053905493576
335 4542815357117005739
336 4681357578020241298
337 4823690730042662489
338 4969906736381228033
339 5120099464626560424
340 5274364761908634173
341 5432800490570250183
342 5595506564374617708
343 5762584985253421963
344 5934139880601812403
345 6110277541126803978
346 6291106459255641299
347 6476737368110733618
348 6667283281057826834
349 6862859531834137388
350 7063583815263231904
351 7269576228563495771
352 7480959313257093544
353 7697858097686384071
354 7920400140144813629
355 8148715572629371076
356 8382937145221750099
357 8623200271105425061
358 8869643072225908724
359 9122406425601522251
360 9381634010292070369
361 9647472355032877408
362 9920070886541703119
363 10199581978506120718
364 10486161001259003504
365 10779966372149830658
366 11081159606619587448
367 11389905369987100043
368 11706371529954710478
369 12030729209841263013
370 12363152842550439193
371 12703820225282545344
372 13052912574997923033
373 13410614584640220179
374 13777114480127828028
375 14152604078121857099
376 14537278844579093471
377 14931337954098445414
378 15334984350069459371
379 15748424805631553674
380 16171869985452688126
381 16605534508336257704
382 17049637010665069136
383 17504400210691329979
384 17970050973681651076
385 18446820377926134899
386 18934943781620694293
387 19434660890631818524
388 19946215827153076303
389 20469857199262718609
390 21005838171391817668
391 21554416535712452363
392 22115854784455524653
393 22690420183167866268
394 23278384844918370023
395 23880025805462955558
396 24495625099378255164
397 25125469837173981598
398 25769852283394016424
399 26429069935716334443
400 27103425605061957194
401 27793227496723206321
402 28498789292521605809
403 29220430234005860696
404 29958475206700418869
405 30713254825415201951
406 31485105520627171084
407 32274369625944473611
408 33081395466663997259
409 33906537449433239426
410 34750156153027480579
411 35612618420253332578
412 36494297450989814954
413 37395572896378194788
414 38316830954171908864
415 39258464465257970203
416 40220873011361344928
417 41204463013943869663
418 42209647834309364333
419 43236847874926680308
420 44286490681982509323
421 45359011049175864509
422 46454851122766231188
423 47574460507887471819
424 48718296376139656633
425 49886823574471079064
426 51080514735362803071
427 52299850388328177854
428 53545319072739844296
429 54817417451996846714
430 56116650429044553176
431 57443531263260177739
432 58798581688716788486
433 60182332033838776189
434 61595321342461849801
435 63038097496310716784
436 64511217338907698513
437 66015246800925623659
438 67550761026998435548
439 69118344504003043019
440 70718591190826038263
441 72352104649628999518
442 74019498178626191323
443 75721394946388570298
444 77458428127688100118
445 79231241040896475488
446 81040487286952451504
447 82886830889912071803
448 84770946439096186364
449 86693519232849747723
450 88655245423927472709
451 90656832166520555596
452 92698997764939217799
453 94782471823965978921
454 96907995400894634084
455 99076321159270023051
456 101288213524343777669
457 103544448840261335636
458 105845815528995610519
459 108193114251042810326
460 110587158067895999764
461 113028772606312104598
462 115518796224388160264
463 118058080179462711083
464 120647488797858371074
465 123287899646481662473
466 125980203706296353633
467 128725305547686624008
468 131524123507726490413
469 134377589869372035703
470 137286651042593088428
471 140252267747461109899
472 143275415199210153443
473 146357083295287869434
474 149498276804413638963
475 152700015557661028754
476 155963334641581870146
477 159289284593389375644
478 162678931598217817696
479 166133357688476405979
480 169653660945315111576
481 173240955702220298999
482 176896372750758140061
483 180621059548483897124
484 184416180429035277251
485 188282916814428173269
486 192222467429573222708
487 196236048519031731019
488 200324894066029621393
489 204490256013748189904
490 208733404488910561583
491 213055628027682860398
492 217458233803909223968
493 221942547859699912178
494 226509915338391877688
495 231161700719901285643
496 235899288058487589694
497 240724081222948891733
498 245637504139268433529
499 250641001035732189728
500 255736036690537653449
501 260924096681914027971
502 266206687640774160764
503 271585337505918679371
504 277061595781812912399
505 282637033798957303126
506 288313244976872147979
507 294091845089717617386
508 299974472534570142254
509 305962788602376375576
510 312058477751606065424
511 318263247884625302843
512 324578830626811735924
513 331006981608433469603
514 337549480749313499509
515 344208132546301657468
516 350984766363576176063
517 357881236725797109953
518 364899423614133982468
519 372041232765190157323
520 379308595972846567133
521 386703471393047562764
522 394227843851551780423
523 401883725154671056774
524 409673154403020556268
525 417598198308303409294
526 425660951513153294696
527 433863536914058535659
528 442208105987391413946
529 450696839118566543969
530 459331945934352285201
531 468115665638359308984
532 477050267349730573861
533 486138050445057102159
534 495381344903544089676
535 504782511655452019979
536 514343942933837595003
537 524068062629619434354
538 533957326649993636963
539 544014223280224440514
540 554241273548835356378
541 564641031596226300628
542 575216085046742385088
543 585969055384220176283
544 596902598331037374608
545 608019404230692011023
546 619322198433937404109
547 630813741688499266388
548 642496830532401495419
549 654374297690927332333
550 666449012477242718164
551 678723881196708826571
552 691201847554910900329
553 703885893069430668296
554 716779037485389769439
555 729884339194791760926
556 743204895659690438264
557 756743843839212346986
558 770504360620461517464
559 784489663253334607051
560 798703009789274786934
561 813147699523992864813
562 827827073444184288809
563 842744514678270832848
564 857903448951195919169
565 873307345043302689563
566 888959715253324093468
567 904864115865514418123
568 921024147620951843623
569 937443456193041763918
570 954125732667250773563
571 971074714025101379354
572 988294183632457655878
573 1005787971732132224464
574 1023559955940845096048
575 1041614061750565080059
576 1059954263034264623596
577 1078584582556119107899
578 1097509092486181792421
579 1116731914919565760684
580 1136257222400164386551
581 1156089238448942004569
582 1176232238096826633636
583 1196690548422236769419
584 1217468549093274427701
585 1238570672914616788164
586 1260001406379138956023
587 1281765290224300527414
588 1303866919993328813508
589 1326310946601231747974
590 1349102076905673672648
591 1372245074282747367083
592 1395744759207675859058
593 1419606009840477725113
594 1443833762616629762753
595 1468433012842761089128
596 1493408815297412894749
597 1518766284836898255143
598 1544510597006296578284
599 1570646988655617441163
600 1597180758561168744979
601 1624117268052164295146
602 1651461941642606089619
603 1679220267668476776946
604 1707397798930277923954
605 1736000153340949912076
606 1765033014579209461024
607 1794502132748340958811
608 1824413325040477958024
609 1854772476406411379751
610 1885585540230961148669
611 1916858539013948165508
612 1948597565056803706419
613 1980808781154853522693
614 2013498421295314098804
615 2046672791361038711883
616 2080338269840051121473
617 2114501308540904904768
618 2149168433313906639503
619 2184346244778241324238
620 2220041419055038613968
621 2256260708506418637794
622 2293010942480556354808
623 2330299028062803594379
624 2368131950832908117678
625 2406516775628369228549
626 2445460647313969653721
627 2484970791557523604864
628 2525054515611881128121
629 2565719209103229040499
630 2606972344825728946876
631 2648821479542533026379
632 2691274254793218472511
633 2734338397707681667654
634 2778021721826533369451
635 2822332127928036384074
636 2867277604861627399518
637 2912866230388064850824
638 2959106172026244888528
639 3006005687906727721659
640 3053573127632016807268
641 3101816933143633559763
642 3150745639596030455253
643 3200367876237385608668
644 3250692367297322104623
645 3301727932881595566833
646 3353483489873793655364
647 3405968052844091386123
648 3459190734965106372749
649 3513160748934898297468
650 3567887407907157124519
651 3623380126428624777446
652 3679648421383795209884
653 3736701912946938008446
654 3794550325541490875944
655 3853203488806866553451
656 3912671338572719950634
657 3972963917840721465361
658 4034091377773882685809
659 4096063978693480881176
660 4158892091083628900629
661 4222586196603537314303
662 4287156889107515845004
663 4352614875672761354763
664 4418970977634979866539
665 4486236131631890318178
666 4554421390654657963203
667 4623537925107305551138
668 4693597023874150638858
669 4764610095395317603908
670 4836588668750373150848
671 4909544394750134322459
672 4983489047036698249088
673 5058434523191743091519
674 5134392845853149855533
675 5211376163839994979764
676 5289396753285963822571
677 5368467018781235398429
678 5448599494522888939796
679 5529806845473883086539
680 5612101868530658731801
681 5695497493699416780664
682 5780006785281122306111
683 5865642943065286815614
684 5952419303532580571176
685 6040349341066327135834
686 6129446669172932550488
687 6219725041711301776459
688 6311198354131295271398
689 6403880644721278799069
690 6497786095864819807113
691 6592929035306583941168
692 6689323937427485498673
693 6786985424529145861323
694 6885928268127714181468
695 6986167390257104834763
696 7087717864781706389079
697 7190594918718617078078
698 7294813933569462006939
699 7400390446661847557498
700 7507340152500508700534
701 7615678904128205164096
702 7725422714496422648624
703 7836587757845935522171
704 7949190371097287672284
705 8063247055251248435051
706 8178774476799300766469
707 8295789469144219066636
708 8414309034030794313319
709 8534350342986764408201
710 8655930738774007886564
711 8779067736850059389323
712 8903779026840005545189
713 9030082474018820160308
714 9157996120804197862999
715 9287538188259945602198
716 9418727077609991649908
717 9551581371763072010358
718 9686119836848154391688
719 9822361423760660149803
720 9960325269719544868578
721 10100030699835298495849
722 10241497228688926210593
723 10384744561921971453384
724 10529792597837642809613
725 10676661429013106693079
726 10825371343923008036396
727 10975942828574281454219
728 11128396568152315605571
729 11282753448678533742554
730 11439034558679453694451
731 11597261190867290798674
732 11757454843832167553186
733 11919637223745994028924
734 12083830246078083345376
735 12250056037322566777819
736 12418336936737673330808
737 12588695498096938879319
738 12761154491452410246493
739 12935736904909909855204
740 13112465946416426859683
741 13291365045559700933173
742 13472457855380065158068
743 13655768254194614736203
744 13841320347433768508913
745 14029138469490290549168
746 14219247185580839361519
747 14411671293620112499758
748 14606435826107654687104
749 14803566052027397799378
750 15003087478760001348024
751 15205025854008062376971
752 15409407167734263965214
753 15616257654112531805621
754 15825603793492268609849
755 16037472314375736369376
756 16251890195408656783529
757 16468884667384100447011
758 16688483215259735671804
759 16910713580188508101451
760 17135603761562822559599
761 17363182019072298859318
762 17593476874775173585099
763 17826517115183420145578
764 18062331793361659681934
765 18300950231039935704568
766 18542402020740425619088
767 18786717027918162591803
768 19033925393115841494868
769 19284057534132782961923
770 19537144148208129876533
771 19793216214218350907964
772 20052304994889126001823
773 20314442039021689026849
774 20579659183733703073668
775 20847988556714744196619
776 21119462578496469685821
777 21394113964737547253484
778 21671975728523421816071
779 21953081182680996852294
780 22237463942108307616076
781 22525157926119263783534
782 22816197360803539413736
783 23110616781401688404459
784 23408451034695563926426
785 23709735281414120622529
786 24014504998654678662353
787 24322795982319729046904
788 24634644349569359863813
789 24950086541289383499439
790 25269159324575245121228
791 25591899795231793051403
792 25918345380288991961563
793 26248533840533660127058
794 26582503273057312290083
795 26920292113820189991298
796 27261939140231561541434
797 27607483473746374116788
798 27956964582478340775744
799 28310422283829545507483
800 28667896747136649738864
801 29029428496333784041071
802 29395058412632209094029
803 29764827737216830283796
804 30138778073959650626139
805 30516951392150247028301
806 30899390029243355220564
807 31286136693623649009611
808 31677234467387799826889
809 32072726809143902867176
810 32472657556828356435359
811 32877070930540281443038
812 33286011535393568320984
813 33699524364386638938698
814 34117654801290011448344
815 34540448623551756297163
816 34967952005220931980118
817 35400211519889089432973
818 35837274143649934295273
819 36279187258077236602768
820 36725998653221077799713
821 37177756530622525293179
822 37634509506346825104028
823 38096306614035203502539
824 38563197307975368850823
825 39035231466190805209134
826 39512459393548949598971
827 39994931824888345152474
828 40482699928164862715046
829 40975815307617083806384
830 41474330006950938184176
831 41978296512543689594619
832 42487767756667363634636
833 43002797120731711992219
834 43523438438546807673701
835 44049745999605366169964
836 44581774552384887857623
837 45119579307669717276089
838 45663215941893115267108
839 46212740600499440309899
840 46768209901326535732373
841 47329680938008419827108
842 47897211283398376249783
843 48470858993012542427638
844 49050682608494094056228
845 49636741161098124114278
846 50229094175197315178824
847 50827801671808504176043
848 51432924172140239057234
849 52044522701161427244313
850 52662658791191176044929
851 53287394485509925593896
852 53918792341991975235069
853 54556915436759504616071
854 55201827367858191127404
855 55853592258954525677451
856 56512274763054929155699
857 57177940066246772298186
858 57850653891461402031699
859 58530482502259277736626
860 59217492706637321232594
861 59911751860858584656108
862 60613327873304340765344
863 61322289208348700574043
864 62038704890255863584104
865 62762644507100106254983
866 63494178214708614717373
867 64233376740627268108868
868 64980311388109479280403
869 65735054040128199994213
870 66497677163411198106868
871 67268253812499714604619
872 68046857633830608732833
873 68833562869842099836704
874 69628444363103214906703
875 70431577560467051199374
876 71243038517247963682096
877 72062903901422787429314
878 72891250997856205477496
879 73728157712550373026699
880 74573702576918909258126
881 75427964752085368419429
882 76291024033206302212761
883 77162960853819025904704
884 78043856290214200962201
885 78933792065833347404499
886 79832850555691399447868
887 80741114790824418407499
888 81658668462762577209503
889 82585595928028531255334
890 83521982212661290771243
891 84467913016765710166538
892 85423474719087710316478
893 86388754381615350078568
894 87363839754205863744848
895 88348819279238781527483
896 89343782096295250570564
897 90348818046863674377523
898 91364017679071788940949
899 92389472252445294259868
900 93425273742693160328719
901 94471514846519727082321
902 95528288986463718182084
903 96595690315764288930571
904 97673813723254229004269
905 98762754838280441098076
906 99862610035651816979559
907 100973476440614632856486
908 102095451933855586367484
909 103228635156532597912926
910 104373125515333499451304
911 105529023187562734295403
912 106696429126256191852554
913 107875445065324301664113
914 109066173524723511511089
915 110268717815656274765528
916 111483182045799672580853
917 112709671124562796928863
918 113948290768373020906508
919 115199147505991283151883
920 116462348683856513626123
921 117738002471459328436034
922 119026217866745121791363
923 120327104701546683610594
924 121640773647046471710058
925 122967336219268667932964
926 124306904784601147997696
927 125659592565347495268379
928 127025513645309189075296
929 128404782975398098638239
930 129797516379279414072301
931 131203830559045146382964
932 132623843100918328785611
933 134057672480988052113789
934 135505438070975467510676
935 136967260144030890029259
936 138443259880562137198713
937 139933559374094237047384
938 141438281637160640506623
939 142957550607226073554494
940 144491491152641164894088
941 146040229078628985397818
942 147603891133303635986648
943 149182605013721021051723
944 150776499371961944965318
945 152385703821247669668413
946 154010348942088071763529
947 155650566288462537983728
948 157306488394033738351889
949 158978248778394416788523
950 160665981953347339371484
951 162369823429218540896971
952 164089909721204010838199
953 165826378355749960246046
954 167579367876966811584859
955 169349017853077053946426
956 171135468882897106535894
957 172938862602353333775136
958 174759341691032355821744
959 176597049878765798755451
960 178452131952249629138364
961 180324733761698218110923
962 182215002227533280641989
963 184123085347107836008908
964 186049132201465336041799
965 187993292962134108125673
966 189955718897957260414308
967 191936562381958197171083
968 193935976898241892614213
969 195954117048932072107028
970 197991138561144449998103
971 200047198293996173881174
972 202122454245651625510868
973 204217065560404729077334
974 206331192535797918010888
975 208464996629777911956779
976 210618640467888456030146
977 212792287850500174932169
978 214986103760077694980321
979 217200254368484187578504
980 219434907044323488126701
981 221690230360319944844599
982 223966394100736152459436
983 226263569268828726185099
984 228581928094342271897251
985 230921644041041708887994
986 233282891814283102063283
987 235665847368623160926994
988 238070687915467563177218
989 240497591930758261223004
990 242946739162699930413408
991 245418310639525718255323
992 247912488677302454382168
993 250429456887775481522103
994 252969400186253268202013
995 255532504799531964412068
996 258118958273860061945219
997 260728949482943321616533
998 263362668635990130058804
999 266020307285797449283403
1000 268702058336877522688849