5 1
6 2
7 5
8 13
9 34
10 89
11 232
12 596
13 1490
14 3588
15 8273
16 18228
17 38403
18 77533
19 150438
20 281403
21 509015
22 892926
23 1523117
24 2532359
25 4112704
26 6536993
27 10186540
28 15586342
29 23449376
30 34731776
31 50700937
32 73018870
33 103843433
34 145950389
35 202879594
36 279108997
37 380260541
38 513342490
39 687033173
40 912011633
41 1201341198
42 1570912553
43 2039953488
44 2631613128
45 3373629118
46 4299086940
47 5447281281
48 6864690152
49 8606073279
50 10735707149
51 13328769998
52 16472890975
53 20269878707
54 24837645526
55 30312344701
56 36850739147
57 44632821260
58 53864704753
59 64781810644
60 77652370874
61 92781274412
62 110514282136
63 131242638265
64 155408107658
65 183508469893
66 216103502693
67 253821488978
68 297366283593
69 347524977593
70 405176199858
71 471299097765
72 546983040661
73 633438091962
74 732006297849
75 844173842744
76 971584124028
77 1116051800810
78 1279577873972
79 1464365857201
80 1672839101276
81 1907659336507
82 2171746500925
83 2468299924598
84 2800820943299
85 3173137017679
86 3589427437102
87 4054250690381
88 4572573588815
89 5149802230168
90 5791814895553
91 6504996974588
92 7296278017678
93 8173171017848
94 9143814028208
95 10217014224873
96 11402294528990
97 12709942905441
98 14151064459797
99 15737636459194
100 17482566406989
101 19399753305333
102 21504152244170
103 23811842459637
104 26340099009401
105 29107468217126
106 32133847043017
107 35440566542240
108 39050479577968
109 42988052960854
110 47279464191884
111 51952702990817
112 57037677797776
113 62566327441015
114 68572738169453
115 75093266254238
116 82166666369383
117 89834225967403
118 98139905871878
119 107130487314973
120 116855725654163
121 127368511008740
122 138725036063121
123 150984971290532
124 164211647857314
125 178472248474884
126 193838006473288
127 210384413377305
128 228191435273202
129 247343738261501
130 267930923298501
131 290047770736802
132 313794494882705
133 339277008896113
134 366607200366434
135 395903217905989
136 427289769110557
137 460898430244946
138 496867968019865
139 535344673834888
140 576482710870948
141 620444474424578
142 667400965885028
143 717532180764433
144 771027511200388
145 828086163359603
146 888917590180765
147 953741939904326
148 1022790520846667
149 1096306282885959
150 1174544316137054
151 1257772367302893
152 1346271374200215
153 1440336018967792
154 1540275300476001
155 1646413126467276
156 1759088925967862
157 1878658282522320
158 2005493588813408
159 2139984723241289
160 2282539749047494
161 2433585636580697
162 2593569009313141
163 2762956914228490
164 2942237617213973
165 3131921424101933
166 3332541528018298
167 3544654883708053
168 3768843109520513
169 4005713417750078
170 4255899574041193
171 4520062886579440
172 4798893225804056
173 5093110075390702
174 5403463615267004
175 5730735837437249
176 6075741695406648
177 6439330288009775
178 6822386078462157
179 7225830149468526
180 7650621495235951
181 8097758351254947
182 8568279562726710
183 9063265992529853
184 9583841969635419
185 10131176778894524
186 10706486193138737
187 11311034048549236
188 11946133864266890
189 12613150507231708
190 13313501903256568
191 14048660795356793
192 14820156550373978
193 15629577014949493
194 16478570421920293
195 17368847348227058
196 18302182725442265
197 19280417904043561
198 20305462772575762
199 21379297932862949
200 22503976932450469
201 23681628555475178
202 24914459173180985
203 26204755155315672
204 27554885343664076
205 28967303588992026
206 30444551352694932
207 31989260374464625
208 33604155407307948
209 35292057021270699
210 37055884477240829
211 38898658672225302
212 40823505157515731
213 42833657231178815
214 44932459106328718
215 47123369156659853
216 49409963240740063
217 51795938106585928
218 54285114878063873
219 56881442624682908
220 59589002016367198
221 62412009064819240
222 65354818953107216
223 68421929955133097
224 71617987446661294
225 74947788009611089
226 78416283631339733
227 82028586000666970
228 85789970902415837
229 89705882712268901
230 93781938993763626
231 98023935199275317
232 102437849476861065
233 107029847584863318
234 111806287916197129
235 116773726634270784
236 121938922922515392
237 127308844349525126
238 132890672351836140
239 138691807836398753
240 144719876904824288
241 150982736701514983
242 157488481387812653
243 164245448244329278
244 171262223903650423
245 178547650715630363
246 186110833247525990
247 193961144921245021
248 202108234790012707
249 210562034456790164
250 219332765136806609
251 228430944866597188
252 237867395861967730
253 247653252027337652
254 257799966618942376
255 268319320064407001
256 279223427941233602
257 290524749116775405
258 302236094052302213
259 314370633273792834
260 326941906012121889
261 339963829015340257
262 353450705535780546
263 367417234494751365
264 381878519827616813
265 396850080012090498
266 412347857782606553
267 428388230033663528
268 444988017915070708
269 462164497122060338
270 479935408383263428
271 498318968149581265
272 517333879487019476
273 536999343176586467
274 557335069024393309
275 578361287385127654
276 600098760902110043
277 622568796467177015
278 645793257403671742
279 669794575875859501
280 694595765528122151
281 720220434357322912
282 746692797821770145
283 774037692190246508
284 802280588134607814
285 831447604569494144
286 861565522742734272
287 892661800580063241
288 924764587287811990
289 957902738217267273
290 992105829994439733
291 1027404175919017898
292 1063828841636326053
293 1101411661086144413
294 1140185252732290778
295 1180183036076903893
296 1221439248463410065
297 1263988962172196206
298 1307868101813054377
299 1353113462018505104
300 1399762725442149224
301 1447854481066240798
302 1497428242822716700
303 1548524468531961857
304 1601184579163632776
305 1655450978423905951
306 1711367072673561997
307 1768977291181360910
308 1828327106717208703
309 1889463056489660819
310 1952432763432353174
311 2017284957843997437
312 2084069499386623211
313 2152837399446796140
314 2223640843864587633
315 2296533216035118868
316 2371569120387549018
317 2448804406246425228
318 2528296192080359768
319 2610102890143047993
320 2694284231511689258
321 2780901291527921765
322 2870016515646431461
323 2961693745696444562
324 3055998246561363049
325 3152996733281852569
326 3252757398587742578
327 3355349940864149285
328 3460845592557282997
329 3569317149025452826
330 3680838997840833401
331 3795487148547610232
332 3913339262882172700
333 4034474685461076298
334 4158974474942548724
335 4286921435667367729
336 4418400149784992252
337 4553497009870882331
338 4692300252040997565
339 4834899989569518518
340 4981388247015890403
341 5131858994867343663
342 5286408184703101678
343 5445133784886541773
344 5608135816791631983
345 5775516391570022648
346 5947379747465228865
347 6123832287680397116
348 6304982618806207022
349 6490941589815517144
350 6681822331631422064
351 6877740297275446633
352 7078813302602662270
353 7285161567630569537
354 7496907758468650901
355 7714177029855557626
356 7937097068310955117
357 8165798135909111765
358 8400413114681377418
359 8641077551654759029
360 8887929704533862809
361 9141110588033534342
362 9400764020869590601
363 9667036673415100640
364 9940078116029734928
365 10220040868069766838
366 10507080447586373708
367 10801355421719949153
368 11103027457798202928
369 11412261375145889623
370 11729225197614072813
371 12054090206836896990
372 12387030996223905671
373 12728225525696010507
374 13077855177173283014
375 13436104810822807709
376 13803162822074902963
377 14179221199416083780
378 14564475582967208977
379 14959125323855323876
380 15363373544387778626
381 15777427199037271652
382 16201497136246537480
383 16635798161061468313
384 17080549098601529234
385 17535972858376397789
386 18002296499457829957
387 18479751296515826146
388 18968572806728242865
389 19469000937573068113
390 19981280015512651298
391 20505658855579251653
392 21042390831871342653
393 21591733948970183858
394 22153950914286245913
395 22729309211345149128
396 23318081174022851140
397 23920544061739894626
398 24536980135624601892
399 25167676735655179409
400 25812926358790772004
401 26473026738101583443
402 27148280922908257565
403 27838997359940791942
404 28545489975527334251
405 29268078258823290151
406 30007087346091250462
407 30762848106042324845
408 31535697226249548983
409 32325977300644112464
410 33134036918105235169
411 33960230752154600972
412 34804919651766338966
413 35668470733303624240
414 36551257473593052448
415 37453659804148025033
416 38376064206552464998
417 39318863809016266553
418 40282458484113965813
419 41267254947718203978
420 42273666859139639093
421 43302114922485047565
422 44353026989245442106
423 45426838162126118677
424 46523990900130631329
425 47644935124910780574
426 48790128328394788073
427 49960035681705918000
428 51155130145383893432
429 52375892580921544526
430 53622811863629214076
431 54896384996839535297
432 56197117227465286360
433 57525522162923116303
434 58882121889436027469
435 60267447091727590574
436 61682037174120959887
437 63126440383055847811
438 64601213931036710390
439 66106924122025487933
440 67644146478292338043
441 69213465868737891868
442 70815476638700658353
443 72450782741263295668
444 74119997870071563818
445 75823745593679867708
446 77562659491437395640
447 79337383290928954361
448 81148571006984698362
449 82996887082273048149
450 84883006529491189669
451 86807615075167644978
452 88771409305091502585
453 90775096811382994697
454 92819396341220207826
455 94905037947236812901
456 97032763139605801157
457 99203325039824312650
458 101417488536214745273
459 103676030441157433624
460 105979739650070289004
461 108329417302150894202
462 110725876942896649556
463 113169944688418670065
464 115662459391565237068
465 118204272809870712203
466 120796249775345926013
467 123439268366126158678
468 126134220079992935923
469 128882010009785969183
470 131683557020721675598
471 134539793929634820365
472 137451667686159931391
473 140420139555869244072
474 143446185305384042369
475 146530795389476371164
476 149674975140178204158
477 152879744957915261320
478 156146140504682780112
479 159475212899280655401
480 162868028914625474126
481 166325671177157082417
482 169849238368357434965
483 173439845428399589018
484 177098623761944818429
485 180826721446105936709
486 184625303440595032042
487 188495551800073931701
488 192438665888725828265
489 196455862597066615478
490 200548376561014597513
491 204717460383237351808
492 208964384856794642528
493 213290439191096399078
494 217696931240194891948
495 222185187733430356513
496 226756554508449434240
497 231412396746615920071
498 236154099210833424557
499 240983066485799679614
500 245900723220712337559
501 250908514374446234363
502 256007905463222209830
503 261200382810787699677
504 266487453801129437251
505 271870647133738725876
506 277351513081449866577
507 282931623750872450180
508 288612573345438347538
509 294395978431084356884
510 300283478204591593064
511 306276734764602829657
512 312377433385339131746
513 318587282793037244365
514 324908015445129329413
515 331341387812186772098
516 337889180662649906753
517 344553199350365641153
518 351335274104955088258
519 358237260325033444613
520 365261038874304485453
521 372408516380552177890
522 379681625537552045401
523 387082325409925049192
524 394612601740956884884
525 402274467263405726354
526 410069962013321582468
527 418001153646900566865
528 426070137760397515892
529 434279038213120525251
530 442630007453531111901
531 451125226848473844262
532 459766907015559420795
533 468557288158725314583
534 477498640406998239614
535 486593264156482833069
536 495843490415601087047
537 505251681153607202816
538 514820229652402680865
539 524551560861676600748
540 534448131757396185958
541 544512431703672890848
542 554746982818029388928
543 565154340340092984713
544 575737093003741114678
545 586497863412724746793
546 597439308419795632565
547 608564119509363510506
548 619875023183709505477
549 631374781352782114429
550 643066191727602315674
551 654952088217304485973
552 667035341329839957425
553 679318858576370194382
554 691805584879376719401
555 704498502984515066576
556 717400633876240190472
557 730515037197230909310
558 743844811671641112028
559 757393095532205610369
560 771163066951228669224
561 785157944475483401087
562 799380987465050363661
563 813835496536123853390
564 828524814007814541983
565 843452324352977257843
566 858621454653092869718
567 874035675057233385853
568 889698499245139538443
569 905613484894440280268
570 921784234152043778033
571 938214394109729645140
572 954907657283972315386
573 971867762100025618412
574 989098493380298777624
575 1006603682837054211769
576 1024387209569457682378
577 1042453000565011490885
578 1060805031205401591397
579 1079447325776789647826
580 1098383957984581227401
581 1117619051472701486457
582 1137156780347409868850
583 1157001369705685502373
584 1177157096168215144149
585 1197628288417015692154
586 1218419327737723446777
587 1239534648566582473656
588 1260978739042164586940
589 1282756141561853640618
590 1304871453343126984628
591 1327329326989667112113
592 1350134471062336694428
593 1373291650655050371323
594 1396805687975576835133
595 1420681462931304919798
596 1444923913720007578115
597 1469538037425637803791
598 1494528890619190728622
599 1519901589964666299469
600 1545661312830167114639
601 1571813297904166174808
602 1598362845816979479745
603 1625315319767478578812
604 1652676146155078360526
605 1680450815217035544376
606 1708644881671093516592
607 1737263965363509330665
608 1766313751922498873118
609 1795799993417136375329
610 1825728509021744633109
611 1856105185685812477242
612 1886935978809476220301
613 1918226912924601987765
614 1949984082381506024778
615 1982213652041350253813
616 2014921857974250543033
617 2048115008163135330278
618 2081799483213392433353
619 2115981737068342063648
620 2150668297730574247088
621 2185865767989189043990
622 2221580826152978147596
623 2257820226789586629857
624 2294590801470693792464
625 2331899459523252271159
626 2369753188786824732013
627 2408159056377057689630
628 2447124209455332169127
629 2486655876004631126251
630 2526761365611663733126
631 2567448070255286830877
632 2608723465101264044755
633 2650595109303403252388
634 2693070646811113291409
635 2736157807183420988964
636 2779864406409489792482
637 2824198347735681478596
638 2869167622499202615240
639 2914780310968377650713
640 2961044583189590702898
641 3007968699840938321853
642 3055561013092635699653
643 3103829967474219002658
644 3152784100748586703313
645 3202432044792922991153
646 3252782526486546545890
647 3303844368605728159301
648 3355626490725520897117
649 3408137910128646697234
650 3461387742721483506329
651 3515385203957197263368
652 3570139609766063245540
653 3625660377493021499842
654 3681957026842511291876
655 3739039180830629712401
656 3796916566744659791812
657 3855599017110013682995
658 3915096470664636683933
659 3975418973340918083014
660 4036576679255155022219
661 4098579851704615786247
662 4161438864172249139166
663 4225164201339086544365
664 4289766460104384318423
665 4355256350613552985008
666 4421644697293921311073
667 4488942439898382724428
668 4557160634556972029238
669 4626310454836420554128
670 4696403192807738086368
671 4767450260121870165065
672 4839463189093479526406
673 4912453633792900714777
674 4986433371146317095029
675 5061414302044209723274
676 5137408452458127756373
677 5214427974565830303725
678 5292485147884849849082
679 5371592380414527594901
680 5451762209786571307201
681 5533007304424186465022
682 5615340464709831745385
683 5698774624161650102128
684 5783322850618626925144
685 5868998347434526995374
686 5955814454680662180412
687 6043784650357542045761
688 6132922551615459787640
689 6223241915984066124783
690 6314756642610984018893
691 6407480773509517326318
692 6501428494815506717103
693 6596614138053386431843
694 6693052181411495681718
695 6790757251026698732733
696 6889744122278367951515
697 6990027721091784327036
698 7091623125251010220337
699 7194545565721289332724
700 7298810427981029121994
701 7404433253363421136028
702 7511429740407754973560
703 7619815746220481823097
704 7729607287846083772826
705 7840820543647805326901
706 7953471854698303806757
707 8067577726180275560050
708 8183154828797115144473
709 8300220000193664899049
710 8418790246387112561554
711 8538882743208094837477
712 8660514837752065073381
713 8783704049840983435690
714 8908468073495388244793
715 9034824778416907363928
716 9162792211481268792588
717 9292388598241869865178
718 9423632344443964707348
719 9556542037549529854833
720 9691136448272868192748
721 9827434532127011627115
722 9965455430980983154941
723 10105218474627979254422
724 10246743182364533772819
725 10390049264580724746239
726 10535156624361485842958
727 10682085359099084380045
728 10830855762116828121887
729 10981488324304063328776
730 11134003735762526784001
731 11288422887464114788892
732 11444766872920132376990
733 11603056989862086260968
734 11763314741934085289104
735 11925561840396912452009
736 12089820205843832744942
737 12256111969928201456401
738 12424459477102937719765
739 12594885286371928431578
740 12767412173053427907613
741 12942063130555518916133
742 13118861372163700996778
743 13297830332840672243253
744 13478993671038370998473
745 13662375270522344182038
746 13847999242208509241865
747 14035889926012376994496
748 14226071892710802892032
749 14418569945816334527814
750 14613409123464223467884
751 14810614700312169770913
752 15010212189452867835680
753 15212227344339422492327
754 15416686160723704531501
755 15623614878607715144126
756 15833039984208029023927
757 16044988211933386164955
758 16259486546375502667238
759 16476562224313171145309
760 16696242736729721616739
761 16918555830843914030932
762 17143529512154333882321
763 17371192046497362636740
764 17601571962118794985138
765 17834698051759175224948
766 18070599374752925356328
767 18309305259141337768153
768 18550845303799505677058
769 18795249380577264772013
770 19042547636454219806853
771 19292770495708930173890
772 19545948662102328783201
773 19802113121075448864417
774 20061295141961533600834
775 20323526280212603799429
776 20588838379640559094893
777 20857263574672888481090
778 21128834292623066259417
779 21403583255975709790376
780 21681543484686575732276
781 21962748298497471749362
782 22247231319266160970820
783 22535026473311336782033
784 22826167993772745830164
785 23120690422986537427619
786 23418628614875917839197
787 23720017737357188241766
788 24024893274761245449115
789 24333291030270624799223
790 24645247128372164906558
791 24960798017325374288173
792 25279980471646580179303
793 25602831594608940161888
794 25929388820758397537953
795 26259689918445661689068
796 26593772992374294973190
797 26931676486164988021056
798 27273439184936105605952
799 27619100217900585573129
800 27968699060979273628374
801 28322275539430777099273
802 28679869830497921097525
803 29041522466070890826282
804 29407274335367144092901
805 29777166687628178404701
806 30151241134833237343322
807 30529539654430041232085
808 30912104592082627430353
809 31298978664436385909294
810 31690204961900376084649
811 32085826951447011204112
812 32485888479429196909736
813 32890433774415010919390
814 33299507450040011095708
815 33713154507877259496193
816 34131420340325150324168
817 34554350733513130027103
818 34981991870225398116493
819 35414390332842677611918
820 35851593106302144341183
821 36293647581075604658515
822 36740601556166011473686
823 37192503242122408816637
824 37649401264073395494699
825 38111344664779198732844
826 38578382907702449021553
827 39050565880097747731860
828 39527943896120119392922
829 40010567699952440864076
830 40498488468951939970776
831 40991757816815856512057
832 41490427796766358886250
833 41994550904754809921573
834 42504180082685475838949
835 43019368721658772615954
836 43540170665234144363177
837 44066640212712668667481
838 44598832122439484200690
839 45136801615126136237093
840 45680604377192936068853
841 46230296564131430654938
842 46785934803887079186553
843 47347576200262233600248
844 47915278336339520418908
845 48489099277925721650698
846 49069097577016252826740
847 49655332275280336609841
848 50247862907566970758972
849 50846749505431789587419
850 51452052600684918406589
851 52063833228959920802358
852 52682152933303938946595
853 53307073767789127503087
854 53938658301145482044526
855 54576969620415163255501
856 55222071334628418555567
857 55874027578501203136440
858 56532903016154602768193
859 57198762844856161091004
860 57871672798783214471534
861 58551699152808337866392
862 59238908726307005499376
863 59933368886987570524265
864 60635147554743668210878
865 61344313205529147558913
866 62060934875255636611733
867 62785082163712847110778
868 63516825238511724500653
869 64256234839050549665173
870 65003382280504099145738
871 65758339457835970965365
872 66521178849834183554521
873 67291973523170155648582
874 68070797136481175401289
875 68857723944476467333984
876 69652828802066966116688
877 70456187168518906554230
878 71267875111631339528652
879 72087969311937684028001
880 72916547066931425771376
881 73753686295316073320727
882 74599465541279482951405
883 75453963978792663935838
884 76317261415933176277959
885 77189438299233233320139
886 78070575718052622029382
887 78960755408976554155421
888 79860059760238561840115
889 80768571816168551645188
890 81686375281666131353873
891 82613554526699324291428
892 83550194590828786299778
893 84496381187757640892708
894 85452200709907048510088
895 86417740233017626182553
896 87393087520776834311890
897 88378331029472447667101
898 89373559912672228091717
899 90378864025929916814434
900 91394333931517664652529
901 92420060903185018795793
902 93456136930944585257890
903 94502654725884486482117
904 95559707725007733989501
905 96627390096098636359026
906 97705796742616363232537
907 98795023308615786440520
908 99895166183695719749508
909 101006322507974679137314
910 102128590177094285908644
911 103262067847250435370897
912 104406854940252354198116
913 105563051648609670020115
914 106730758940647617183773
915 107910078565650503044358
916 109101113059033559556523
917 110303965747543305347303
918 111518740754486543867038
919 112745543004988123628653
920 113984478231277586961143
921 115235652978004834119440
922 116499174607584930010081
923 117775151305572181210252
924 119063692086063611376854
925 120364906797131963562224
926 121678906126288358374048
927 123005801605974737338825
928 124345705619086221250982
929 125698731404523513713401
930 127064993062775480499701
931 128444605561532035794122
932 129837684741327466791285
933 131244347321214328565453
934 132664710904468041547194
935 134098893984322324374549
936 135547015949735595315937
937 137009197091188475893086
938 138485558606512530764265
939 139976222606750378361008
940 141481312122047307205368
941 143000951107574533269518
942 144535264449484234175228
943 146084377970896496467393
944 147648418437918312633368
945 149227513565694764978383
946 150821792024492533906765
947 152431383445815868599086
948 154056418428555158516687
949 155697028545168244607299
950 157353346347894609528694
951 159025505375002586651453
952 160713640157069728047035
953 162417886223296472113372
954 164138380107853251937201
955 165875259356261185940276
956 167628662531806492805482
957 169398729221988773128700
958 171185600045003300693048
959 172989416656257466713849
960 174810321754921520855354
961 176648459090513753273877
962 178503973469520262396581
963 180377010762049453600690
964 182267717908521414414393
965 184176242926392312318153
966 186102734916913961683538
967 188047344071928706846053
968 190010221680699768768773
969 191991520136777203214858
970 193991392944899618809273
971 196009994727931803833240
972 198047481233838411059116
973 200104009342693850398522
974 202179737073728539602644
975 204274823592411663720689
976 206389429217570594490508
977 208523715428547121304395
978 210677844872390645863037
979 212851981371088493101526
980 215046289928833491443251
981 217260936739328975910367
982 219496089193131368093390
983 221751915885030487457293
984 224028586621467748937279
985 226326272427992402254184
986 228645145556755968857217
987 230985379494045032880476
988 233347148967852542979390
989 235730629955487782393928
990 238135999691225165067088
991 240563436673992016129833
992 243013120675095495547278
993 245485232745988824205553
994 247979955226076972204373
995 250497471750561969606938
996 253037967258328000386365
997 255601627999866440796421
998 258188641545241003883882
999 260799196792093152350389
1000 263433483973687942463209