Problem: You have a team of N people. For a particular task, you can pick any non-empty subset of people. The cost of having x people for the task is xk. 

Output the sum of costs over all non-empty subsets of people.

Input

Only line of input contains two integers N (1 ≤ N ≤ 109) representing total number of people and k (1 ≤ k ≤ 5000).

Output

Output the sum of costs for all non empty subsets modulo 109 + 7.

Examples

Input

1 1


Output

1


Input

3 2


Output

24

Note

In the first example, there is only one non-empty subset {1} with cost 11 = 1.

In the second example, there are seven non-empty subsets.

- {1} with cost 12 = 1

- {2} with cost 12 = 1

- {1, 2} with cost 22 = 4

- {3} with cost 12 = 1

- {1, 3} with cost 22 = 4

- {2, 3} with cost 22 = 4

- {1, 2, 3} with cost 32 = 9

The total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24.

Solution (in PYTHON):

Solution:
import sys
range = xrange
input = raw_input

N,K = [int(x) for x in input().split()]

MOD = 10**9+7
coeff = [0]*(5000+1)
coeff[0] = 1

done = 0
if K>=3500:
 done = 3500
 coeff = []
 a = coeff.append
 a(0)
 a(1)
 a(838444402)
 a(929751016)
 a(1984544027)
 a(2956360280)
 a(3889371291)
 a(3388858871)
 a(3126306525)
 a(5822211401)
 a(5357011751)
 a(6087361063)
 a(5474621987)
 a(5843982363)
 a(7443622890)
 a(5265251873)
 a(6656410331)
 a(7868035096)
 a(9863603187)
 a(7526444798)
 a(9942036262)
 a(10946208972)
 a(11645820030)
 a(12310640798)
 a(13046200523)
 a(13739757804)
 a(12726355612)
 a(11534209867)
 a(12348913137)
 a(16706056129)
 a(12380262845)
 a(13631128623)
 a(17540327724)
 a(13774751229)
 a(17146162643)
 a(16664035511)
 a(15776505276)
 a(19839471823)
 a(19071554759)
 a(18117618413)
 a(18810049485)
 a(24793956233)
 a(20850501661)
 a(24110901653)
 a(20591890892)
 a(17612067378)
 a(21310008193)
 a(24845834519)
 a(22911797991)
 a(22907707214)
 a(28314947921)
 a(28739437993)
 a(28755315489)
 a(21344232489)
 a(24256193163)
 a(24874462774)
 a(28875604759)
 a(29370319545)
 a(29471306198)
 a(30560483322)
 a(30404838581)
 a(29276866679)
 a(26281342396)
 a(31446470893)
 a(27572498584)
 a(29695871782)
 a(30082375625)
 a(35345658860)
 a(36801408755)
 a(33206107776)
 a(38006732793)
 a(34089574506)
 a(37470554681)
 a(35737338894)
 a(34255219236)
 a(40474149903)
 a(34085037058)
 a(35305607406)
 a(37959860924)
 a(37819631148)
 a(37153298814)
 a(43829732925)
 a(43747054504)
 a(41578479408)
 a(42852716191)
 a(42339420858)
 a(44328932982)
 a(44062101851)
 a(44406204832)
 a(39412875209)
 a(41659754768)
 a(44283854748)
 a(45394718434)
 a(41404943532)
 a(47116676440)
 a(46982812844)
 a(47522197822)
 a(48280777329)
 a(46947679042)
 a(45405280231)
 a(49300298657)
 a(48246190117)
 a(51199180625)
 a(51186408752)
 a(52006786327)
 a(52074163770)
 a(51096563481)
 a(56191241171)
 a(54151701682)
 a(55828868478)
 a(51021966636)
 a(56397293765)
 a(57338090321)
 a(53634577415)
 a(56318180579)
 a(54479715535)
 a(58952307111)
 a(60369484509)
 a(54557797220)
 a(56627361373)
 a(62748761824)
 a(60004021530)
 a(62136296810)
 a(60342499046)
 a(61446204168)
 a(60245635396)
 a(61534322330)
 a(57109237336)
 a(63802771818)
 a(67698048945)
 a(67664084201)
 a(65547176478)
 a(62372424585)
 a(67467809067)
 a(70322633740)
 a(68449715269)
 a(70319245591)
 a(72677338432)
 a(69096863529)
 a(62375326869)
 a(70186930638)
 a(64787886276)
 a(70508833641)
 a(72792694291)
 a(67578636952)
 a(68918670696)
 a(68497385611)
 a(77244664853)
 a(74532128955)
 a(75602972102)
 a(78827685529)
 a(67565776308)
 a(68346005785)
 a(70535421656)
 a(75431403762)
 a(76930154007)
 a(76741901305)
 a(80563268078)
 a(75448354462)
 a(80122301363)
 a(78747935337)
 a(73841101014)
 a(82548715834)
 a(78738148694)
 a(83810780793)
 a(84811879101)
 a(85559563322)
 a(86364155817)
 a(74845727631)
 a(84619093705)
 a(81875412025)
 a(85212985290)
 a(95474787007)
 a(82858797399)
 a(88891946249)
 a(90421253101)
 a(85784335924)
 a(88054522668)
 a(92166923213)
 a(88518638037)
 a(93172520203)
 a(84503507144)
 a(92143761464)
 a(97689886242)
 a(89110606125)
 a(93468567063)
 a(91361787641)
 a(92481646213)
 a(89941944720)
 a(96097741171)
 a(92522718472)
 a(91235362511)
 a(100438303984)
 a(99125051233)
 a(100644370404)
 a(101014550106)
 a(99314973807)
 a(97255866724)
 a(94976327379)
 a(95381632206)
 a(103894813488)
 a(103876729483)
 a(97859109300)
 a(97891357025)
 a(97011238359)
 a(104644349083)
 a(100106245046)
 a(103546333647)
 a(109309690840)
 a(107095891648)
 a(104985496600)
 a(97780055585)
 a(101397497236)
 a(108828664175)
 a(101111352985)
 a(101157241757)
 a(106912430674)
 a(107891399434)
 a(107442866978)
 a(104107562146)
 a(114681627772)
 a(112057721484)
 a(106073169385)
 a(115832283143)
 a(111737215340)
 a(113306395102)
 a(113946430827)
 a(117890125217)
 a(113352769612)
 a(108203732119)
 a(117323240971)
 a(112307521248)
 a(115682471069)
 a(113143701143)
 a(119080655169)
 a(117396022016)
 a(116883944425)
 a(119380343404)
 a(112570798930)
 a(118985495735)
 a(111469256185)
 a(118063241776)
 a(122124398360)
 a(120347387425)
 a(125475220312)
 a(122959542597)
 a(123305450418)
 a(126427970977)
 a(122666421015)
 a(120938706216)
 a(128818975094)
 a(119718143314)
 a(126801989839)
 a(129320307248)
 a(120581980108)
 a(127249282759)
 a(127865695079)
 a(131034792597)
 a(126720544248)
 a(133655732646)
 a(126623397343)
 a(123653997808)
 a(131793140992)
 a(127710804907)
 a(131736457929)
 a(135841349935)
 a(128128636551)
 a(135607225202)
 a(139649292701)
 a(139586803962)
 a(145475688185)
 a(127808256085)
 a(137085348950)
 a(133179691094)
 a(132997657739)
 a(124854692874)
 a(132236733595)
 a(131916120827)
 a(138138319424)
 a(141419361136)
 a(141454163783)
 a(144266746729)
 a(136648250849)
 a(147762297880)
 a(145984737955)
 a(136421341585)
 a(139206003030)
 a(138782476900)
 a(146023125483)
 a(152293873596)
 a(144692370311)
 a(142395071994)
 a(143460452806)
 a(146667962360)
 a(150737718454)
 a(142801661180)
 a(145521010520)
 a(138956618433)
 a(157988077803)
 a(147731535569)
 a(148941310650)
 a(150148839271)
 a(145235744725)
 a(148405480747)
 a(150902017783)
 a(150055568942)
 a(147362576884)
 a(149859916405)
 a(154490661611)
 a(160236737289)
 a(149711988096)
 a(151024422548)
 a(158825038767)
 a(156974660839)
 a(160232876615)
 a(161432823861)
 a(168484142456)
 a(156986073735)
 a(159255061662)
 a(163183608104)
 a(157071807992)
 a(156224199254)
 a(166812865001)
 a(164990840670)
 a(162416618817)
 a(157453142045)
 a(167169403858)
 a(156906233743)
 a(160971225750)
 a(167588672591)
 a(156707137898)
 a(165699942282)
 a(161294185696)
 a(173208033697)
 a(163369898277)
 a(154926578182)
 a(176881055983)
 a(166009701356)
 a(170904949501)
 a(176961521909)
 a(168511876796)
 a(168676614616)
 a(169437923384)
 a(166311379666)
 a(177016951316)
 a(168596171375)
 a(170621482482)
 a(171308693012)
 a(179223062022)
 a(165328090815)
 a(172923499935)
 a(175023904077)
 a(174550862706)
 a(179626902856)
 a(182979285828)
 a(169291151702)
 a(176853553332)
 a(188635034746)
 a(175411928242)
 a(179119357085)
 a(186667186637)
 a(191614598586)
 a(181600291378)
 a(176605532567)
 a(182651194224)
 a(183713113810)
 a(181753413583)
 a(182352920989)
 a(190292604021)
 a(182663901910)
 a(188982345027)
 a(183548068148)
 a(180096450258)
 a(187945945606)
 a(181436311624)
 a(196427780096)
 a(183044820478)
 a(183676814948)
 a(184876357629)
 a(197230883461)
 a(189007270525)
 a(188565446977)
 a(189299669925)
 a(184328858256)
 a(187846152674)
 a(190664265761)
 a(187648038203)
 a(197910054085)
 a(202002265500)
 a(199719670330)
 a(186597808313)
 a(204253647266)
 a(204115587762)
 a(198794597496)
 a(193336711999)
 a(197016168374)
 a(197900305644)
 a(197454322110)
 a(193846933648)
 a(203239695206)
 a(212612305370)
 a(197198731785)
 a(206407389681)
 a(201049204930)
 a(193124498956)
 a(205273404472)
 a(206374097242)
 a(196820044577)
 a(202376775112)
 a(195139710065)
 a(200675033351)
 a(211897968665)
 a(199928868318)
 a(203580146305)
 a(199779836707)
 a(208037444445)
 a(198888988263)
 a(195726468609)
 a(200638124176)
 a(205685442736)
 a(213770837172)
 a(219830175891)
 a(210035271736)
 a(212175785266)
 a(207069505102)
 a(213806939689)
 a(221541047679)
 a(213594105684)
 a(217459137473)
 a(216888463021)
 a(216526188701)
 a(210054099277)
 a(214871588621)
 a(213796385818)
 a(221352018070)
 a(212934558019)
 a(215478030748)
 a(221596641435)
 a(206425410529)
 a(220290000941)
 a(218555506822)
 a(216467916554)
 a(228698698509)
 a(217781982849)
 a(218265794230)
 a(217475562020)
 a(233977805917)
 a(216847164338)
 a(221301616014)
 a(218989759341)
 a(218667311703)
 a(226227848168)
 a(210642379625)
 a(226548888247)
 a(217379138130)
 a(233783360859)
 a(221725466637)
 a(242333137943)
 a(219832345177)
 a(220232291802)
 a(225076372340)
 a(230188487531)
 a(229564444360)
 a(226469694206)
 a(242523764585)
 a(224564009984)
 a(241428360414)
 a(235351502864)
 a(238742200371)
 a(236213100699)
 a(245119075059)
 a(230832986904)
 a(231595039211)
 a(246469178475)
 a(238471254714)
 a(242705173790)
 a(249886633220)
 a(240560163640)
 a(243540266096)
 a(237651333816)
 a(232095844633)
 a(226228354310)
 a(233262703799)
 a(247490993770)
 a(243526808255)
 a(242068837611)
 a(250561970929)
 a(244575941368)
 a(239555423257)
 a(245889804412)
 a(221071596795)
 a(246099843009)
 a(253776449818)
 a(252903119611)
 a(256832469865)
 a(240870011109)
 a(250303858515)
 a(242483612392)
 a(248517628439)
 a(244821501376)
 a(254291248915)
 a(260279593580)
 a(246831881644)
 a(249747652733)
 a(259027407379)
 a(256488562245)
 a(250177991133)
 a(247382750324)
 a(257432752601)
 a(250371568548)
 a(249548355934)
 a(263498263051)
 a(253456016679)
 a(262945128928)
 a(256027943047)
 a(261902934160)
 a(249288747048)
 a(260464419099)
 a(255050927871)
 a(248939266380)
 a(264877489621)
 a(247177984167)
 a(267051067608)
 a(248105598121)
 a(258612941386)
 a(260335126376)
 a(273001581275)
 a(253898903214)
 a(269612102010)
 a(249618675845)
 a(267277673162)
 a(270556496984)
 a(278446734181)
 a(264258520442)
 a(269753653707)
 a(271486141189)
 a(266763009198)
 a(264558302844)
 a(262538019382)
 a(261833615576)
 a(277437562462)
 a(268192136210)
 a(269842821718)
 a(271682685925)
 a(257004573460)
 a(276796856764)
 a(270640575336)
 a(260634775456)
 a(275161404589)
 a(269814155373)
 a(255425366643)
 a(274150730212)
 a(285650028759)
 a(256758437404)
 a(277402483525)
 a(279076670214)
 a(282069753484)
 a(271243644400)
 a(286366573265)
 a(276668694165)
 a(264447215267)
 a(280382303631)
 a(278215093327)
 a(273663585522)
 a(298052458676)
 a(279013595898)
 a(277583453637)
 a(288073429517)
 a(283230218833)
 a(284191150684)
 a(289717758023)
 a(296491015696)
 a(285235636272)
 a(298211283943)
 a(286318925910)
 a(291233481582)
 a(283748250983)
 a(302713592751)
 a(296498777599)
 a(289255020398)
 a(295678203987)
 a(294266422058)
 a(281511104789)
 a(275665363340)
 a(295869527777)
 a(298720940134)
 a(283912876026)
 a(290759818974)
 a(288430547229)
 a(287191517644)
 a(291803130332)
 a(303159762782)
 a(296194024652)
 a(294638389245)
 a(295405145322)
 a(303458699672)
 a(289351018865)
 a(293812346380)
 a(291288649393)
 a(311470157968)
 a(293281446730)
 a(293391680118)
 a(292104393222)
 a(305220753385)
 a(303566735261)
 a(306729737118)
 a(293580727517)
 a(302714894128)
 a(316176495386)
 a(312626811343)
 a(292286595273)
 a(306922692790)
 a(311121780561)
 a(318095090500)
 a(310159608882)
 a(293335823447)
 a(301057557874)
 a(293952139201)
 a(318071683843)
 a(298811592534)
 a(312267185673)
 a(305715555816)
 a(308375972879)
 a(308848067188)
 a(311844174029)
 a(301216107655)
 a(316899626335)
 a(313844249295)
 a(319895898612)
 a(317694355784)
 a(316126580986)
 a(311498896907)
 a(317270676481)
 a(305667364715)
 a(319471779158)
 a(314781755725)
 a(325892693459)
 a(325959569439)
 a(312920703665)
 a(320883689698)
 a(318874343057)
 a(315965334032)
 a(315977901571)
 a(322960976842)
 a(318789102946)
 a(319553946234)
 a(316331905785)
 a(325720734054)
 a(333192019251)
 a(328363943243)
 a(325283638821)
 a(330424300577)
 a(317457842093)
 a(322388919985)
 a(320440712484)
 a(324820063501)
 a(324779591505)
 a(329171591377)
 a(334940046045)
 a(329509513159)
 a(342754862990)
 a(319409022167)
 a(333376101977)
 a(331927379274)
 a(338462658007)
 a(339990409062)
 a(338861928662)
 a(328709183732)
 a(327154720049)
 a(332342503426)
 a(328640064765)
 a(346424484368)
 a(347393068055)
 a(336660351278)
 a(335750759596)
 a(334426380930)
 a(334157139432)
 a(326000803645)
 a(346755536243)
 a(328279467841)
 a(335731381993)
 a(351697986506)
 a(342787280651)
 a(342347524430)
 a(338437501698)
 a(336228994439)
 a(345340441207)
 a(355657883500)
 a(348602682137)
 a(327168535997)
 a(348147767666)
 a(346335793067)
 a(345405568090)
 a(338405747050)
 a(351806463065)
 a(353149189283)
 a(343642510251)
 a(331422125649)
 a(360464241748)
 a(344387229124)
 a(333139487013)
 a(351502486129)
 a(334753488292)
 a(343281454723)
 a(350511354680)
 a(360403005122)
 a(352124449355)
 a(358930422412)
 a(360179353621)
 a(364303887497)
 a(358533258004)
 a(361008370317)
 a(352067863798)
 a(358299760009)
 a(348231708290)
 a(361686069369)
 a(363064038643)
 a(365526879718)
 a(365180774289)
 a(346825204740)
 a(348490595827)
 a(348250854633)
 a(358482640066)
 a(353701675609)
 a(367440239699)
 a(367256837150)
 a(367610740555)
 a(360136526950)
 a(372998388479)
 a(374424962433)
 a(367282628049)
 a(371914759739)
 a(354690116961)
 a(365359646635)
 a(354461655600)
 a(369379562849)
 a(366956845593)
 a(363540425673)
 a(369847557149)
 a(371148068930)
 a(359206903076)
 a(374662439574)
 a(372203274175)
 a(370088174531)
 a(378121028256)
 a(376189340331)
 a(370424997079)
 a(376037428839)
 a(376298255428)
 a(365022662401)
 a(381613116778)
 a(381591322792)
 a(374194604496)
 a(385861758338)
 a(379427345545)
 a(367539779684)
 a(386523111660)
 a(368821532803)
 a(368916503318)
 a(380908007734)
 a(380272847256)
 a(395327124856)
 a(366615185574)
 a(376511145470)
 a(387481934611)
 a(394649472011)
 a(385062883898)
 a(382151920336)
 a(383143923975)
 a(384485066026)
 a(388213803786)
 a(382092037676)
 a(378719878885)
 a(393015721908)
 a(386342406781)
 a(390064400034)
 a(382751543415)
 a(384504763983)
 a(376464145271)
 a(399388595418)
 a(383923635526)
 a(390519743731)
 a(399939547046)
 a(392787589700)
 a(397430237027)
 a(394286252028)
 a(396772138916)
 a(400402616450)
 a(387861785355)
 a(384573467417)
 a(404026993848)
 a(388869669559)
 a(388756256600)
 a(400092690358)
 a(383144420364)
 a(390921136697)
 a(402809265218)
 a(404159273739)
 a(400055714868)
 a(404399949643)
 a(403108096734)
 a(400146975631)
 a(397276942640)
 a(408073707187)
 a(388480449284)
 a(408110435870)
 a(404701441262)
 a(389814615719)
 a(407915677231)
 a(403380710346)
 a(405557253387)
 a(389960863844)
 a(407892992895)
 a(405918658099)
 a(418796427849)
 a(403102042053)
 a(403370421113)
 a(413574442982)
 a(400568454891)
 a(406077039170)
 a(397589603017)
 a(407391071755)
 a(412939155524)
 a(414085884831)
 a(417296120134)
 a(413706960513)
 a(415581904780)
 a(416095989448)
 a(422828937858)
 a(405601632690)
 a(420482955115)
 a(412024554393)
 a(417059415334)
 a(421600030519)
 a(416367952293)
 a(436858607676)
 a(426002713259)
 a(413078257754)
 a(424048389172)
 a(409148240082)
 a(398923510947)
 a(421133076609)
 a(421175604027)
 a(420241606161)
 a(412019103829)
 a(435509077027)
 a(419557257858)
 a(432771232486)
 a(419240850650)
 a(424105954568)
 a(417133762580)
 a(424307093663)
 a(409197857712)
 a(437203200879)
 a(423933381007)
 a(436864714499)
 a(440597932360)
 a(428722381280)
 a(427673781170)
 a(435703045055)
 a(412000542249)
 a(440097681684)
 a(426900028170)
 a(434899258363)
 a(427254963861)
 a(437759701293)
 a(436846114622)
 a(451272467390)
 a(423402939923)
 a(444255062846)
 a(427707652442)
 a(454042142390)
 a(432741175529)
 a(442281942907)
 a(451524719468)
 a(446965023446)
 a(429075424525)
 a(439384121363)
 a(435151589076)
 a(427171226092)
 a(428524086822)
 a(432706461481)
 a(448069761850)
 a(444476028801)
 a(444208257255)
 a(439861266692)
 a(437417683139)
 a(458948298599)
 a(451411209826)
 a(453957544653)
 a(468643328135)
 a(447504525820)
 a(448490591584)
 a(444269350521)
 a(455443422775)
 a(447061175308)
 a(434417812742)
 a(447978251856)
 a(467227297417)
 a(444259209618)
 a(443485875892)
 a(440558445301)
 a(452163295829)
 a(457822200720)
 a(436018356171)
 a(448414548679)
 a(454342021584)
 a(456931171169)
 a(464157597167)
 a(458557524099)
 a(451488328950)
 a(441346449116)
 a(448978714759)
 a(450605081736)
 a(458774102548)
 a(465634310804)
 a(449062419674)
 a(462727355172)
 a(464527574169)
 a(469648507460)
 a(474836142302)
 a(463915077660)
 a(460888454709)
 a(438035816493)
 a(435367633549)
 a(450863593157)
 a(451969854093)
 a(471196935723)
 a(462138582230)
 a(452821964665)
 a(466902459078)
 a(447339838292)
 a(455431575568)
 a(463364830230)
 a(485392780327)
 a(468350027290)
 a(476915850008)
 a(462342346283)
 a(456883577363)
 a(456619699951)
 a(466445745403)
 a(463088664026)
 a(468909316092)
 a(465208544784)
 a(469759026504)
 a(471871919483)
 a(468007493238)
 a(472420219797)
 a(456718754422)
 a(474072414986)
 a(466704957543)
 a(482337924687)
 a(479471802643)
 a(490097666276)
 a(473831745424)
 a(474547734161)
 a(478109883410)
 a(483740605719)
 a(480008000739)
 a(485454453590)
 a(484409395839)
 a(496841134284)
 a(473021376163)
 a(484757445418)
 a(484155987256)
 a(486588856179)
 a(483896380147)
 a(488133715216)
 a(491520715075)
 a(499745848312)
 a(472948646131)
 a(468723109617)
 a(479970356837)
 a(481931304807)
 a(491209065248)
 a(491428732158)
 a(494422369746)
 a(501312849663)
 a(500350281211)
 a(485256761513)
 a(497692474304)
 a(485773899478)
 a(481995676858)
 a(503609388854)
 a(482472284266)
 a(492886192270)
 a(499327970577)
 a(505535630925)
 a(495117149681)
 a(481257683906)
 a(495113476087)
 a(502142659001)
 a(498699723369)
 a(495540224642)
 a(508631678959)
 a(506681282406)
 a(491703604486)
 a(506391189509)
 a(483467868150)
 a(493845655736)
 a(501818549236)
 a(505077170310)
 a(500826890561)
 a(507303311286)
 a(513156453022)
 a(527189240587)
 a(507790164039)
 a(506950235014)
 a(511497996813)
 a(502681146353)
 a(502570872940)
 a(499609178565)
 a(491791630158)
 a(496378806092)
 a(505657292491)
 a(511456868913)
 a(510403577186)
 a(508888973391)
 a(512722643332)
 a(509113360505)
 a(508306562924)
 a(500878199286)
 a(513288442231)
 a(508255473708)
 a(509252281431)
 a(530618091570)
 a(500728549449)
 a(512036796053)
 a(529127015940)
 a(529936992926)
 a(508076247144)
 a(530382113020)
 a(501820621006)
 a(525483662255)
 a(521326735113)
 a(519321116503)
 a(523402631726)
 a(526136516220)
 a(513355742465)
 a(502774371222)
 a(536244584092)
 a(511500639713)
 a(521146796215)
 a(527349817191)
 a(517704018885)
 a(526100324711)
 a(531975739816)
 a(513878706515)
 a(538074644467)
 a(526048924466)
 a(533788306512)
 a(525615605758)
 a(529404129292)
 a(525245019189)
 a(532747789287)
 a(531161382558)
 a(515199013180)
 a(527183717879)
 a(532982119683)
 a(534539588099)
 a(516294745242)
 a(545136163564)
 a(546735565677)
 a(533755542499)
 a(515525023409)
 a(540987747460)
 a(523753811851)
 a(534086050053)
 a(536367705415)
 a(535490108047)
 a(529068532844)
 a(535899067185)
 a(538727760194)
 a(530544082549)
 a(545930193933)
 a(535593340285)
 a(535014238486)
 a(544385758975)
 a(553417031562)
 a(521287427305)
 a(512009925747)
 a(539154056172)
 a(540454782706)
 a(546185787614)
 a(536447439446)
 a(544638785740)
 a(549024574631)
 a(530095129241)
 a(520706477110)
 a(536566166878)
 a(555217793441)
 a(545830647700)
 a(544692353397)
 a(536791635689)
 a(543315792538)
 a(534324420076)
 a(537691844193)
 a(559513204768)
 a(555387804698)
 a(557405986824)
 a(536260394924)
 a(536202037068)
 a(551444513607)
 a(549806381745)
 a(545379501061)
 a(538678558355)
 a(551013957469)
 a(552475688061)
 a(552853647974)
 a(564663250649)
 a(570853107246)
 a(558279985999)
 a(579034047793)
 a(564657233938)
 a(562023893934)
 a(566853521581)
 a(563847745915)
 a(553318075174)
 a(561355096409)
 a(555410608013)
 a(562658947893)
 a(558898989322)
 a(571321131647)
 a(558046767863)
 a(564097921816)
 a(562747963508)
 a(561487473472)
 a(559904226609)
 a(585057632390)
 a(575541781329)
 a(575183528768)
 a(578524048872)
 a(569455103325)
 a(560580697939)
 a(573051091665)
 a(577856320037)
 a(575227933581)
 a(568445466213)
 a(566337120995)
 a(571645945357)
 a(570350640205)
 a(576689839604)
 a(557688406055)
 a(549952856523)
 a(581842097799)
 a(580344778834)
 a(578112421748)
 a(573503642714)
 a(575403355145)
 a(556722767707)
 a(567736752747)
 a(591236571943)
 a(581058685571)
 a(577354803754)
 a(585767453302)
 a(561940173267)
 a(567360324028)
 a(561923267690)
 a(577547454418)
 a(578809740077)
 a(582305162733)
 a(575120607498)
 a(571547271767)
 a(590086914509)
 a(573015953469)
 a(583513947042)
 a(587370591892)
 a(581471539371)
 a(595000299984)
 a(593091639206)
 a(576651845769)
 a(587625491837)
 a(608309122750)
 a(571631153196)
 a(569974954868)
 a(575696163110)
 a(572919674484)
 a(586603046811)
 a(587951988110)
 a(585484981642)
 a(573895852106)
 a(596723952766)
 a(591011355291)
 a(583454900884)
 a(573551993648)
 a(583711229699)
 a(612051054129)
 a(593932494082)
 a(607676926482)
 a(596139853345)
 a(603912046325)
 a(594415523067)
 a(599489022607)
 a(599303581178)
 a(605234197978)
 a(604909298686)
 a(599824001988)
 a(588005766735)
 a(603334785679)
 a(603732195659)
 a(611596904130)
 a(604469657393)
 a(593197189788)
 a(606770615740)
 a(593648625534)
 a(604546873594)
 a(602240477366)
 a(616557975144)
 a(611518220856)
 a(594517805660)
 a(605182288051)
 a(618057218364)
 a(602320273836)
 a(590441272429)
 a(608205322507)
 a(607029231821)
 a(621771758258)
 a(624248500863)
 a(614865164026)
 a(628654287015)
 a(601318371145)
 a(617061839862)
 a(626630532044)
 a(598058166145)
 a(625877016968)
 a(608683680896)
 a(587292147359)
 a(613491856339)
 a(616978545596)
 a(599973335675)
 a(603710445541)
 a(606769064662)
 a(612439887375)
 a(603943705798)
 a(621443062305)
 a(628611372058)
 a(617086472351)
 a(623895769907)
 a(626796031835)
 a(605501411337)
 a(636453185262)
 a(629112297600)
 a(618437229016)
 a(626189428166)
 a(628877294878)
 a(611790547396)
 a(624308665180)
 a(621311336246)
 a(615370579018)
 a(617765966256)
 a(615792771640)
 a(622315433015)
 a(616781295877)
 a(624254156798)
 a(635885692449)
 a(628270842619)
 a(611822036059)
 a(620804506178)
 a(604192916862)
 a(624166610334)
 a(628214112730)
 a(630375095379)
 a(632819574536)
 a(622228682658)
 a(615698950100)
 a(655198936097)
 a(629337594943)
 a(621408909906)
 a(624931248576)
 a(641037018989)
 a(637933066719)
 a(641392864200)
 a(628262945250)
 a(639910833018)
 a(648179992821)
 a(632902004251)
 a(651585487690)
 a(633058731403)
 a(631521749028)
 a(618239515445)
 a(645516606017)
 a(644577954740)
 a(652441156587)
 a(649406053763)
 a(664049475593)
 a(658282636309)
 a(635822061551)
 a(639348727350)
 a(643590786393)
 a(640400711393)
 a(668727875250)
 a(638434231840)
 a(648812408908)
 a(665326491998)
 a(646442569391)
 a(650122051947)
 a(654452665269)
 a(643506704927)
 a(653367083971)
 a(644572272480)
 a(662548850801)
 a(632819196863)
 a(637345269645)
 a(635686356104)
 a(662170241644)
 a(645810442083)
 a(667544332914)
 a(640212938099)
 a(668576350657)
 a(645661730623)
 a(652539037257)
 a(670768004888)
 a(659455244114)
 a(654698868180)
 a(653449439560)
 a(649864264725)
 a(660072439302)
 a(649552674501)
 a(682631624813)
 a(657142498169)
 a(655022949337)
 a(670156830125)
 a(669301011631)
 a(672803249812)
 a(666370421580)
 a(653604941089)
 a(659053540252)
 a(673414197996)
 a(673919250657)
 a(652375255525)
 a(665118555408)
 a(664914497369)
 a(668845605254)
 a(672525506517)
 a(656698445541)
 a(684895519288)
 a(657086261163)
 a(667111333298)
 a(662175736301)
 a(686310816877)
 a(688094976419)
 a(669176050106)
 a(655007288439)
 a(658266022196)
 a(669964962603)
 a(665008567737)
 a(688926336228)
 a(681070978549)
 a(664996288605)
 a(697481194561)
 a(675019987068)
 a(658902296594)
 a(662513221841)
 a(666791399388)
 a(665629876735)
 a(678966664048)
 a(670763884774)
 a(674185395199)
 a(694286051938)
 a(690669382802)
 a(670029390458)
 a(674483052141)
 a(672842693688)
 a(688849623711)
 a(684809690631)
 a(684349439081)
 a(706722335446)
 a(692235043162)
 a(674884036606)
 a(685349639639)
 a(677412323152)
 a(691351358579)
 a(685669985913)
 a(681847623408)
 a(684337700008)
 a(676986740794)
 a(671859806775)
 a(686921849292)
 a(669172766113)
 a(703364362041)
 a(699200005752)
 a(696672178928)
 a(673118760927)
 a(704032658950)
 a(686253667599)
 a(686114590713)
 a(701617044602)
 a(686820406483)
 a(708902399339)
 a(702244244083)
 a(703720543984)
 a(686027767300)
 a(700196995857)
 a(695509411844)
 a(696522120963)
 a(691800984416)
 a(689873762908)
 a(715508067984)
 a(702728209815)
 a(712785407027)
 a(698679830706)
 a(704433625817)
 a(712979060939)
 a(702765510021)
 a(699261178718)
 a(682442389958)
 a(696710264542)
 a(716410412606)
 a(719186636359)
 a(722971977894)
 a(697820624368)
 a(706767058105)
 a(693358061790)
 a(704454034353)
 a(699890107156)
 a(703067317998)
 a(706096903672)
 a(710519967061)
 a(707975568978)
 a(704309636897)
 a(705345603045)
 a(718999786940)
 a(689320673559)
 a(729342494989)
 a(709219037376)
 a(725514166486)
 a(723667852571)
 a(714343025821)
 a(714343747350)
 a(704432388034)
 a(727320750675)
 a(707551930199)
 a(726023100391)
 a(697092183486)
 a(723778157665)
 a(717224180126)
 a(725084169366)
 a(705993139981)
 a(728339454703)
 a(708474021694)
 a(705626625767)
 a(738138698006)
 a(721895468926)
 a(712991377260)
 a(694575831401)
 a(728594890547)
 a(708002137528)
 a(715759161250)
 a(727983547160)
 a(702543627145)
 a(720762631729)
 a(732729653966)
 a(718436947040)
 a(735666813016)
 a(714724220474)
 a(729540384856)
 a(733287814029)
 a(728408245358)
 a(739299616371)
 a(718552118048)
 a(728070834593)
 a(737451621689)
 a(738845278338)
 a(735541594464)
 a(731957089307)
 a(738949404757)
 a(727496265545)
 a(742673189367)
 a(729982740604)
 a(748758330275)
 a(736468615858)
 a(734130673948)
 a(730740654742)
 a(755309813507)
 a(725788882309)
 a(730972676843)
 a(729590062703)
 a(725954987725)
 a(730472757076)
 a(729947066088)
 a(720212726527)
 a(727680229084)
 a(724536759848)
 a(747244479566)
 a(757197526883)
 a(744949086426)
 a(736917485409)
 a(737127532068)
 a(748578640844)
 a(734164627023)
 a(758083886269)
 a(756106361936)
 a(710855630853)
 a(756693100886)
 a(763604044869)
 a(750402198603)
 a(734304302614)
 a(766038391920)
 a(747728917145)
 a(752537108841)
 a(740434331859)
 a(757372943754)
 a(744638988425)
 a(740377403639)
 a(749686878501)
 a(751325158198)
 a(732664922229)
 a(743227895999)
 a(753059702564)
 a(764051358600)
 a(756592831239)
 a(762213803490)
 a(759577928793)
 a(739937942708)
 a(738462853437)
 a(755569974615)
 a(746166869530)
 a(746295612740)
 a(755983984210)
 a(744519028746)
 a(769428711202)
 a(752113756791)
 a(765731236299)
 a(743582252418)
 a(769604835333)
 a(775944444342)
 a(752458763437)
 a(773978902357)
 a(760766897503)
 a(757329676333)
 a(764253018874)
 a(773924563039)
 a(770210813825)
 a(768462330636)
 a(785395070475)
 a(740890695505)
 a(798770525513)
 a(773081854456)
 a(766964649508)
 a(748994997332)
 a(766768235047)
 a(769822027527)
 a(769370034963)
 a(764171541594)
 a(777987897127)
 a(779092838097)
 a(777870782567)
 a(793945980676)
 a(784999411119)
 a(769161367400)
 a(751516233713)
 a(775145517516)
 a(767432823473)
 a(772540606233)
 a(778975552835)
 a(795467536666)
 a(773996640267)
 a(796279295195)
 a(780990254630)
 a(793708870026)
 a(766351109417)
 a(776242221073)
 a(778312690732)
 a(778909485794)
 a(758123267140)
 a(777482452377)
 a(787782854901)
 a(775459616986)
 a(773613738354)
 a(770824801827)
 a(805514295539)
 a(786300685461)
 a(791720501016)
 a(796478809938)
 a(783457943056)
 a(783283961747)
 a(787729296907)
 a(797720187630)
 a(800346783619)
 a(790205789424)
 a(803465793583)
 a(779864891441)
 a(795395144244)
 a(790541385212)
 a(784031594567)
 a(791122857560)
 a(774135236730)
 a(801193829772)
 a(802670571108)
 a(807125152087)
 a(785757447080)
 a(774700966476)
 a(782205574457)
 a(814558924401)
 a(794914992743)
 a(805458314786)
 a(804697024272)
 a(792084135032)
 a(793648543636)
 a(822913359421)
 a(805253129715)
 a(793395903780)
 a(817116649034)
 a(798968326993)
 a(789305297685)
 a(802386119975)
 a(807680581648)
 a(817509246340)
 a(787951880697)
 a(808535038148)
 a(802053107280)
 a(797658527486)
 a(799288578943)
 a(830024020847)
 a(802141570106)
 a(831737919290)
 a(809588310525)
 a(785071689017)
 a(819214827266)
 a(805143840029)
 a(821542078007)
 a(802166737605)
 a(816769468222)
 a(812840095544)
 a(826455593670)
 a(819676337185)
 a(810611630925)
 a(809312059410)
 a(787493307794)
 a(828728417976)
 a(819692969215)
 a(814782712197)
 a(839442910312)
 a(817956647900)
 a(799306990178)
 a(805378908834)
 a(806670020949)
 a(836115141053)
 a(809307186262)
 a(830410340080)
 a(807429270618)
 a(821026355182)
 a(842044494906)
 a(821082951934)
 a(823067962977)
 a(819220667073)
 a(818709331073)
 a(828675533791)
 a(823974806910)
 a(818223803383)
 a(809519142018)
 a(819963385513)
 a(820667971104)
 a(822447280333)
 a(818391331783)
 a(838450883206)
 a(828280907498)
 a(828144651072)
 a(822062985265)
 a(831765703078)
 a(838861253197)
 a(834506532937)
 a(827910281148)
 a(812683447204)
 a(834661402206)
 a(865754112352)
 a(844098925303)
 a(851168490190)
 a(811841236808)
 a(820067514076)
 a(845649991443)
 a(842146276599)
 a(841248225714)
 a(847220271259)
 a(850629079045)
 a(840557576386)
 a(826076438370)
 a(841780716701)
 a(824203331707)
 a(840699694979)
 a(831153447457)
 a(829684501421)
 a(843327690763)
 a(828415009821)
 a(850036570609)
 a(849098163885)
 a(863372835551)
 a(822322632585)
 a(841043177422)
 a(822552914517)
 a(852755936820)
 a(859086237365)
 a(813813794936)
 a(833539219721)
 a(839585191185)
 a(849496916142)
 a(873445133554)
 a(850552475517)
 a(863075684189)
 a(830421101027)
 a(852160275864)
 a(835958939027)
 a(855727804561)
 a(857626157896)
 a(851147054532)
 a(865791039480)
 a(838541940060)
 a(844617644422)
 a(842744665437)
 a(850280844844)
 a(869933551065)
 a(854869889876)
 a(851909908260)
 a(844671490037)
 a(846775285682)
 a(847699208851)
 a(863668323396)
 a(870992151743)
 a(864521595567)
 a(863885221892)
 a(865051409730)
 a(865506584012)
 a(860420765674)
 a(866377376913)
 a(857234460644)
 a(844244515864)
 a(849848501203)
 a(846935868494)
 a(840880154908)
 a(868069340778)
 a(865065321293)
 a(892629755572)
 a(849644179460)
 a(859717778664)
 a(865404828745)
 a(869851560027)
 a(877861853235)
 a(881133251415)
 a(884320075575)
 a(870626515831)
 a(870614511953)
 a(876013339630)
 a(855443781761)
 a(875278440362)
 a(858986632898)
 a(869405183232)
 a(850918528579)
 a(876135456649)
 a(874252357702)
 a(883559679409)
 a(883785095819)
 a(879790536618)
 a(873599879668)
 a(857244242100)
 a(858230165942)
 a(858321761729)
 a(887416398023)
 a(900779099246)
 a(870624988564)
 a(868131143834)
 a(878450390088)
 a(873281737646)
 a(879457801429)
 a(884192546210)
 a(871712766537)
 a(877146722645)
 a(886229844401)
 a(895393730239)
 a(862602131134)
 a(889973043413)
 a(892728379453)
 a(876207922664)
 a(908493239668)
 a(899482700368)
 a(866641988623)
 a(857653533294)
 a(886619940670)
 a(902951684950)
 a(904273195629)
 a(893185412899)
 a(906448054503)
 a(886192926425)
 a(883647479736)
 a(888318724183)
 a(853009328097)
 a(887189319221)
 a(881020284141)
 a(893337562073)
 a(885282764765)
 a(893602872753)
 a(908293124788)
 a(902068857049)
 a(879721840814)
 a(906482488591)
 a(895652250029)
 a(893284857352)
 a(895003299464)
 a(884732790667)
 a(878090524524)
 a(881008768744)
 a(896323042247)
 a(906913381292)
 a(907331621441)
 a(914032561352)
 a(878094722739)
 a(902584396205)
 a(922377022314)
 a(900438992419)
 a(889344275292)
 a(893502254195)
 a(911838397177)
 a(900872054406)
 a(896816481514)
 a(899566934854)
 a(925321687431)
 a(873773328987)
 a(902684012389)
 a(934868324240)
 a(921867546546)
 a(914330220860)
 a(916023053376)
 a(920562633002)
 a(918330803588)
 a(922539581596)
 a(900419925548)
 a(907311375030)
 a(896006460649)
 a(902161570528)
 a(915854507636)
 a(920568163477)
 a(920819559905)
 a(913715281193)
 a(914944619755)
 a(920288725783)
 a(909195901200)
 a(909077691135)
 a(916804867518)
 a(910476436180)
 a(920450156512)
 a(936183267855)
 a(926883428730)
 a(910724392598)
 a(899832260372)
 a(909507914317)
 a(947950259921)
 a(922086980689)
 a(916171034602)
 a(929264099340)
 a(926944971218)
 a(919895201770)
 a(937882067168)
 a(913690804153)
 a(924444727244)
 a(932818095517)
 a(933352764001)
 a(917268195795)
 a(932563981203)
 a(929013713372)
 a(925081590392)
 a(908904824570)
 a(929629444888)
 a(916456421462)
 a(952989760949)
 a(925721920505)
 a(928764526925)
 a(907344699467)
 a(933947156472)
 a(938266130679)
 a(930809393526)
 a(922136017605)
 a(935707022004)
 a(947465667689)
 a(920998002757)
 a(922284291383)
 a(933448856926)
 a(927293235582)
 a(940124723511)
 a(934330084765)
 a(924304683570)
 a(932223147657)
 a(930006776557)
 a(939796763683)
 a(938190153239)
 a(929170958934)
 a(942610636733)
 a(911159271447)
 a(938976720229)
 a(941302114889)
 a(944536993238)
 a(939096335197)
 a(946809250074)
 a(956851897695)
 a(933879714537)
 a(945791333287)
 a(941578045847)
 a(939899234683)
 a(966043745185)
 a(949145665398)
 a(946062735825)
 a(957229095715)
 a(946760296002)
 a(936840171667)
 a(973965177960)
 a(952062262716)
 a(953725073867)
 a(942299236018)
 a(959829889293)
 a(947563622098)
 a(945540841630)
 a(960036344850)
 a(950111072404)
 a(975408631316)
 a(921419829175)
 a(951337562288)
 a(982656164873)
 a(974379021829)
 a(967310864528)
 a(952535335210)
 a(967625856682)
 a(966529925377)
 a(963905878717)
 a(928727730191)
 a(956806849539)
 a(970826812873)
 a(983480951003)
 a(942330154429)
 a(940648151778)
 a(961878454523)
 a(947890539846)
 a(975618104268)
 a(954116722163)
 a(966870914298)
 a(969774859957)
 a(948565852874)
 a(959890453965)
 a(965711310605)
 a(969965502809)
 a(957391104281)
 a(996238545105)
 a(980194196026)
 a(967933335783)
 a(976382266206)
 a(962795976187)
 a(966812343717)
 a(968931430699)
 a(977616003612)
 a(966961952080)
 a(985302892185)
 a(970579210763)
 a(976614777923)
 a(965347411926)
 a(993277148744)
 a(990872332942)
 a(969371451151)
 a(959012479444)
 a(984740777526)
 a(980288177744)
 a(972695919974)
 a(966843898480)
 a(999066563950)
 a(972390538388)
 a(995944642900)
 a(973812098418)
 a(992562401090)
 a(989486432654)
 a(978128011067)
 a(979569366538)
 a(971984002896)
 a(977581709478)
 a(970972368094)
 a(985431595851)
 a(979437198553)
 a(975711215946)
 a(992483836447)
 a(969700803251)
 a(998147417146)
 a(990464614761)
 a(977281535667)
 a(991213935512)
 a(980265974812)
 a(986065886070)
 a(977145333569)
 a(995600667232)
 a(964473623964)
 a(1006770223168)
 a(999979985527)
 a(980052794451)
 a(987478104458)
 a(967769532525)
 a(964158491039)
 a(1030226711941)
 a(989009727594)
 a(1019028114907)
 a(1002263609005)
 a(1007564014523)
 a(983884553306)
 a(1006292274920)
 a(1009125828568)
 a(989466808043)
 a(995222438964)
 a(981090417208)
 a(1003212722648)
 a(981956274535)
 a(1002221933407)
 a(1015157883342)
 a(1005879656264)
 a(986269254016)
 a(989081519251)
 a(995784281035)
 a(1021750003782)
 a(1003318998612)
 a(1001559382174)
 a(1013962629518)
 a(1042031969911)
 a(1011754501439)
 a(1002889917246)
 a(1009759206949)
 a(1001015175198)
 a(1002386217667)
 a(989057122496)
 a(1016418453021)
 a(1024635937878)
 a(1033427635506)
 a(1014850029511)
 a(1017775740425)
 a(1028924927319)
 a(1018333130578)
 a(1022230715287)
 a(982855722011)
 a(1026686506146)
 a(1015854281172)
 a(1010553617173)
 a(1010688512629)
 a(1030331817982)
 a(1026953549562)
 a(1023068642921)
 a(1014887733687)
 a(1023049518668)
 a(1014991036805)
 a(1014477948579)
 a(1015792631272)
 a(1001724790930)
 a(1049682175226)
 a(1008860696025)
 a(1017867980030)
 a(1009073598993)
 a(1011926758178)
 a(1021718323911)
 a(1040484007615)
 a(1022123285332)
 a(1034034817286)
 a(1020407436830)
 a(1048673114257)
 a(1033969484419)
 a(1010323223005)
 a(1017822750147)
 a(1021465852657)
 a(1031089765899)
 a(1029536179238)
 a(1041223006832)
 a(1048565862056)
 a(1013827426127)
 a(1026399502474)
 a(1009196261618)
 a(1029394532315)
 a(1041119561709)
 a(996836666925)
 a(1029372022290)
 a(1033279590148)
 a(1013587261665)
 a(1038750504311)
 a(1022676239007)
 a(1018712200414)
 a(1055600311595)
 a(1058537075467)
 a(1037249686683)
 a(1033865348789)
 a(1035195267332)
 a(1005988166597)
 a(1043613055773)
 a(1029534470227)
 a(1054724721246)
 a(1048308608143)
 a(1039864899409)
 a(1009656941059)
 a(1039003478863)
 a(1039589607400)
 a(1033508551781)
 a(1035791214035)
 a(1048594960849)
 a(1039097688738)
 a(1053422331936)
 a(1046338257289)
 a(1060124528870)
 a(1060882741364)
 a(1039261138443)
 a(1061409957410)
 a(1055277271335)
 a(1058448545828)
 a(1063742067790)
 a(1058034833716)
 a(1060103419777)
 a(1047022143088)
 a(1030936907893)
 a(1032341253029)
 a(1060208312488)
 a(1051479867903)
 a(1065032433352)
 a(1060080847440)
 a(1048024237475)
 a(1015373691481)
 a(1053247450318)
 a(1056623373570)
 a(1064506200307)
 a(1047683004290)
 a(1056110117484)
 a(1051057623609)
 a(1070648159252)
 a(1052468360417)
 a(1033851253999)
 a(1067086783799)
 a(1042131127534)
 a(1053727831025)
 a(1040366952932)
 a(1074330495887)
 a(1037939566935)
 a(1054416346796)
 a(1079898232104)
 a(1060087261264)
 a(1088058631406)
 a(1048864101484)
 a(1065630705945)
 a(1060670965733)
 a(1061266699920)
 a(1062652579953)
 a(1079471455063)
 a(1062200444578)
 a(1075107565608)
 a(1065282924540)
 a(1056828409374)
 a(1060471338500)
 a(1088162675621)
 a(1064161545996)
 a(1091363947080)
 a(1075044065223)
 a(1073282809241)
 a(1069417437357)
 a(1082482353539)
 a(1052876422534)
 a(1059167763253)
 a(1065267489141)
 a(1077531213770)
 a(1039297034009)
 a(1059848958747)
 a(1102374062013)
 a(1074651239394)
 a(1094827464270)
 a(1087270774116)
 a(1095706510739)
 a(1084503778849)
 a(1087327064775)
 a(1065381636946)
 a(1090232793536)
 a(1090636780195)
 a(1099965252918)
 a(1090805589891)
 a(1090577195651)
 a(1080597149338)
 a(1079050612876)
 a(1079808804170)
 a(1097615874049)
 a(1111818404976)
 a(1057799965410)
 a(1092669395396)
 a(1077148496824)
 a(1086132318056)
 a(1090633618805)
 a(1108054583353)
 a(1088980204061)
 a(1065362512330)
 a(1096940390879)
 a(1082541899099)
 a(1097685326850)
 a(1090650405508)
 a(1068656381179)
 a(1111607697515)
 a(1090008375656)
 a(1108080647895)
 a(1080798694843)
 a(1059734958522)
 a(1076447616829)
 a(1109278786888)
 a(1087315274317)
 a(1102015209975)
 a(1087658937273)
 a(1085703566638)
 a(1092250695290)
 a(1066932603960)
 a(1101224478370)
 a(1124449545396)
 a(1099139395178)
 a(1099998439236)
 a(1094021162134)
 a(1102955033960)
 a(1103139801225)
 a(1108801075354)
 a(1092429176339)
 a(1127006033189)
 a(1089428567233)
 a(1096913171969)
 a(1112884945231)
 a(1114712736004)
 a(1104411889783)
 a(1115403735619)
 a(1104674507790)
 a(1082226534907)
 a(1121258834239)
 a(1105846420935)
 a(1135699958945)
 a(1094022978523)
 a(1104666551010)
 a(1105097060469)
 a(1109018317780)
 a(1111483803270)
 a(1116217078515)
 a(1104482810718)
 a(1122622679429)
 a(1095964244618)
 a(1135265153341)
 a(1136934784699)
 a(1112289642390)
 a(1106191311294)
 a(1110946720736)
 a(1134556923004)
 a(1119197279959)
 a(1144426652121)
 a(1118670582902)
 a(1129391786177)
 a(1118969727999)
 a(1126023036243)
 a(1135443655128)
 a(1119213765575)
 a(1154005773036)
 a(1130035655075)
 a(1126092000322)
 a(1121438648469)
 a(1120464642127)
 a(1131030189580)
 a(1140712325309)
 a(1134343732899)
 a(1112506650969)
 a(1105904823613)
 a(1118631797063)
 a(1164213689240)
 a(1106617446490)
 a(1112449545775)
 a(1129227565015)
 a(1122396410455)
 a(1127408487638)
 a(1104158086860)
 a(1139297658545)
 a(1146544644183)
 a(1142097284962)
 a(1103727161284)
 a(1135014652400)
 a(1152076580994)
 a(1104499301979)
 a(1157290005363)
 a(1128542203456)
 a(1103473720392)
 a(1152768217716)
 a(1136389413191)
 a(1153640024329)
 a(1150851279652)
 a(1151136086357)
 a(1125626112990)
 a(1142077850472)
 a(1131605940667)
 a(1125588329173)
 a(1142006888314)
 a(1125337270414)
 a(1132280259814)
 a(1136189560523)
 a(1134561958626)
 a(1127313895961)
 a(1148892620778)
 a(1157918620950)
 a(1153055789888)
 a(1116399585486)
 a(1154312060953)
 a(1147367789141)
 a(1123677958960)
 a(1147155417816)
 a(1169078802403)
 a(1153921975373)
 a(1144074789514)
 a(1167098593821)
 a(1166164110111)
 a(1152828381760)
 a(1155960999279)
 a(1163494249876)
 a(1148891595146)
 a(1132574132279)
 a(1147115653314)
 a(1147194653608)
 a(1160078413825)
 a(1163224999042)
 a(1138810526134)
 a(1151450551936)
 a(1142468927487)
 a(1166004440016)
 a(1158042728300)
 a(1153616747649)
 a(1147003077050)
 a(1160954079012)
 a(1174898878775)
 a(1158539925608)
 a(1174440278799)
 a(1151277987790)
 a(1171312957573)
 a(1156002222478)
 a(1162697200796)
 a(1150513776256)
 a(1129010568277)
 a(1151511304622)
 a(1157672040595)
 a(1152343351558)
 a(1140767515909)
 a(1174513979577)
 a(1171815763321)
 a(1160832936835)
 a(1146739748419)
 a(1167337685272)
 a(1162639034325)
 a(1164751950435)
 a(1175116877783)
 a(1183275698261)
 a(1197006299755)
 a(1164984522302)
 a(1173984732270)
 a(1161778174778)
 a(1167197952475)
 a(1165872424415)
 a(1178014714400)
 a(1143890918701)
 a(1149681207225)
 a(1190791259589)
 a(1180893347333)
 a(1169194989564)
 a(1162066938257)
 a(1194824214291)
 a(1174285333175)
 a(1172726253136)
 a(1189710819253)
 a(1190504057951)
 a(1180625816758)
 a(1200664392818)
 a(1172380137156)
 a(1167265450582)
 a(1184917305402)
 a(1158811406804)
 a(1189444223817)
 a(1175355015785)
 a(1178438751952)
 a(1184648389698)
 a(1169400285821)
 a(1170962563907)
 a(1180903502567)
 a(1167663051512)
 a(1188961311973)
 a(1183712706630)
 a(1190228448959)
 a(1184568097334)
 a(1198424084833)
 a(1179936166601)
 a(1166120172717)
 a(1187482862799)
 a(1187442333849)
 a(1188869966280)
 a(1191678527891)
 a(1190854727304)
 a(1195959198370)
 a(1207551992798)
 a(1208193385498)
 a(1184355892362)
 a(1195274629193)
 a(1193892309056)
 a(1194778508639)
 a(1204105682894)
 a(1202954518531)
 a(1191195137775)
 a(1177434158980)
 a(1163783137883)
 a(1212403397604)
 a(1180488230511)
 a(1214063529037)
 a(1185950185639)
 a(1194738559187)
 a(1173061999369)
 a(1186370644445)
 a(1199841350182)
 a(1194508798665)
 a(1181846840013)
 a(1176469048456)
 a(1186362363220)
 a(1191538374281)
 a(1198445396938)
 a(1177406390543)
 a(1199619375633)
 a(1197209126030)
 a(1208183019780)
 a(1205179304758)
 a(1204181677993)
 a(1199678873028)
 a(1190218956760)
 a(1236326561210)
 a(1184174653901)
 a(1196452653866)
 a(1202186621966)
 a(1213574940189)
 a(1222483410130)
 a(1189209029696)
 a(1219323599334)
 a(1200473231295)
 a(1192361629688)
 a(1204971162915)
 a(1206575163129)
 a(1211721870239)
 a(1201955333774)
 a(1191664634061)
 a(1230444112474)
 a(1221347834898)
 a(1217629877339)
 a(1211650091038)
 a(1214103187485)
 a(1202898275031)
 a(1203680776282)
 a(1229597116399)
 a(1207322153576)
 a(1235595166643)
 a(1203992298955)
 a(1237913528029)
 a(1226274284672)
 a(1210103550558)
 a(1255464226089)
 a(1181725609050)
 a(1203546001647)
 a(1223598666520)
 a(1221314692065)
 a(1207495349835)
 a(1244284041660)
 a(1219939812863)
 a(1245017444853)
 a(1218908030849)
 a(1217971195065)
 a(1205471469269)
 a(1217061270124)
 a(1215502851095)
 a(1206359425075)
 a(1236183553555)
 a(1243021908989)
 a(1215604005353)
 a(1228489497333)
 a(1204450980786)
 a(1253965517788)
 a(1221987452144)
 a(1241039069491)
 a(1253617136116)
 a(1241093487678)
 a(1243957651658)
 a(1219570059189)
 a(1255527879361)
 a(1249036991439)
 a(1241983039007)
 a(1238159633544)
 a(1232173859592)
 a(1237710938573)
 a(1248889758763)
 a(1219099722267)
 a(1239682415255)
 a(1242961591261)
 a(1227258601615)
 a(1231975463896)
 a(1230866505238)
 a(1271009272281)
 a(1218922052931)
 a(1271640667315)
 a(1252746066129)
 a(1257789377365)
 a(1253813184883)
 a(1258174243594)
 a(1251852334954)
 a(1280254353225)
 a(1261059355684)
 a(1260815515287)
 a(1264149600610)
 a(1219438372748)
 a(1261210790580)
 a(1218799620004)
 a(1230193406112)
 a(1218629047624)
 a(1273503759050)
 a(1243470819264)
 a(1234154095626)
 a(1218270122435)
 a(1230501953295)
 a(1255041255375)
 a(1252540186622)
 a(1245584106987)
 a(1256209910799)
 a(1280079327530)
 a(1249654561661)
 a(1277161967982)
 a(1246752908697)
 a(1248848274952)
 a(1251523904318)
 a(1241865773868)
 a(1287627177010)
 a(1273375640325)
 a(1251963667831)
 a(1269421669475)
 a(1268509731277)
 a(1252759033959)
 a(1286027387868)
 a(1246492170994)
 a(1260286384402)
 a(1258601446618)
 a(1273550965185)
 a(1264631322479)
 a(1277823503343)
 a(1280701422060)
 a(1296850751912)
 a(1269664284366)
 a(1275767173895)
 a(1270685123362)
 a(1267876026215)
 a(1269089550476)
 a(1297786644600)
 a(1267160852286)
 a(1265661134318)
 a(1245034140834)
 a(1265551663581)
 a(1259554730059)
 a(1269458535056)
 a(1265981821738)
 a(1267786046533)
 a(1276307767800)
 a(1261044242709)
 a(1271100541460)
 a(1282725922155)
 a(1265638593208)
 a(1268907650517)
 a(1274287897004)
 a(1273639567821)
 a(1288282641999)
 a(1293087983837)
 a(1295117611680)
 a(1268614827474)
 a(1271284056911)
 a(1296241318670)
 a(1273406225140)
 a(1279565494173)
 a(1307466566330)
 a(1285191265916)
 a(1296278985485)
 a(1274965364273)
 a(1297720485348)
 a(1266142928209)
 a(1286487531536)
 a(1284895999805)
 a(1271882053341)
 a(1286940711672)
 a(1275599178486)
 a(1283392058841)
 a(1288292338187)
 a(1292078475893)
 a(1302985896674)
 a(1278068855726)
 a(1303799000362)
 a(1275808629990)
 a(1275558016225)
 a(1294513119305)
 a(1291726466356)
 a(1263715113350)
 a(1279142567950)
 a(1319154874184)
 a(1284940774073)
 a(1298258401323)
 a(1284873054431)
 a(1301902387469)
 a(1317022178353)
 a(1307606370023)
 a(1303632406981)
 a(1304026510199)
 a(1287092436549)
 a(1293869520864)
 a(1285310658631)
 a(1303446194729)
 a(1289754467357)
 a(1312158022333)
 a(1305906325564)
 a(1304075679428)
 a(1328124179830)
 a(1304128095780)
 a(1318799303848)
 a(1307745288122)
 a(1332480761361)
 a(1327189087999)
 a(1325816071189)
 a(1329905076793)
 a(1314702124455)
 a(1294485353228)
 a(1299662364072)
 a(1270422067052)
 a(1289341731709)
 a(1278907356961)
 a(1300850177266)
 a(1307889122547)
 a(1312676891877)
 a(1321608152101)
 a(1314438015688)
 a(1310682295520)
 a(1304153681006)
 a(1334848634159)
 a(1336754850735)
 a(1315542202226)
 a(1299179546524)
 a(1321660042054)
 a(1285899651166)
 a(1308560051638)
 a(1324678452734)
 a(1302408372568)
 a(1309386250704)
 a(1307202999274)
 a(1340276849264)
 a(1321063480403)
 a(1299413669790)
 a(1317752472703)
 a(1338709797168)
 a(1337207748486)
 a(1326037512965)
 a(1306123456862)
 a(1343392747724)
 a(1339781018611)
 a(1328065012938)
 a(1315172216305)
 a(1314406447331)
 a(1331432278467)
 a(1333889960253)
 a(1352002274179)
 a(1319778494184)
 a(1333129544930)
 a(1311628376924)
 a(1358491059817)
 a(1358644154076)
 a(1315139321479)
 a(1348582593202)
 a(1320624368657)
 a(1336159214341)
 a(1332373230320)
 a(1342189467067)
 a(1332651144553)
 a(1330413205877)
 a(1355456851239)
 a(1306197854330)
 a(1310251530672)
 a(1330330373508)
 a(1339967812194)
 a(1333353704982)
 a(1332327784844)
 a(1311679901008)
 a(1340011571324)
 a(1341134566521)
 a(1310852063460)
 a(1350464601045)
 a(1361267459936)
 a(1342562162985)
 a(1336839689812)
 a(1351709158278)
 a(1327344846642)
 a(1353688018219)
 a(1337196798832)
 a(1337817518222)
 a(1359365634697)
 a(1314628273025)
 a(1349930486754)
 a(1364566550029)
 a(1340751900627)
 a(1310149458348)
 a(1339670279524)
 a(1334798591044)
 a(1338274405932)
 a(1352012986988)
 a(1361037672740)
 a(1335204512073)
 a(1365947594247)
 a(1343516354444)
 a(1346924563186)
 a(1340082054038)
 a(1347708974909)
 a(1367597681832)
 a(1348579884982)
 a(1354783135586)
 a(1353346791322)
 a(1362884875398)
 a(1333557835802)
 a(1350912867406)
 a(1335924656399)
 a(1321233060396)
 a(1369053461265)
 a(1325565953218)
 a(1345317699724)
 a(1375820825101)
 a(1366120753322)
 a(1354175648662)
 a(1357887660315)
 a(1348964548653)
 a(1362104121287)
 a(1342665659851)
 a(1351537932018)
 a(1357764388324)
 a(1382583971747)
 a(1399072313028)
 a(1368296638376)
 a(1358633804047)
 a(1372740136876)
 a(1346995584105)
 a(1359684783285)
 a(1378402727981)
 a(1359031998394)
 a(1379817990112)
 a(1352660537860)
 a(1389641827110)
 a(1349272034558)
 a(1370161459548)
 a(1376955464503)
 a(1372188158003)
 a(1380095512963)
 a(1361502082969)
 a(1389200500799)
 a(1375453447334)
 a(1349192220071)
 a(1371485214804)
 a(1407074444117)
 a(1386076397147)
 a(1374178417427)
 a(1377607399035)
 a(1372402422698)
 a(1380448421642)
 a(1377312338083)
 a(1356365074632)
 a(1386090392855)
 a(1358470236638)
 a(1364875691887)
 a(1375676274818)
 a(1394509456111)
 a(1388253484053)
 a(1370191092572)
 a(1387710843431)
 a(1376075503439)
 a(1374519461864)
 a(1383367554257)
 a(1375567784630)
 a(1393083888445)
 a(1377086981324)
 a(1384857312130)
 a(1372619579195)
 a(1418607624890)
 a(1379281021874)
 a(1373238757700)
 a(1366857221099)
 a(1392148577910)
 a(1374618445043)
 a(1371191802898)
 a(1391794187545)
 a(1427009438347)
 a(1372757061619)
 a(1406702674366)
 a(1407923460945)
 a(1416685854616)
 a(1376059436301)
 a(1378425504300)
 a(1360193255040)
 a(1395659667265)
 a(1371933576908)
 a(1391651247703)
 a(1361337987386)
 a(1376741490605)
 a(1410352285978)
 a(1385012971474)
 a(1392772076110)
 a(1396018819180)
 a(1410864332460)
 a(1404633926903)
 a(1400220316166)
 a(1386522795542)
 a(1405005887789)
 a(1417838911028)
 a(1410551052779)
 a(1402274982848)
 a(1412253993598)
 a(1374917395497)
 a(1402223739465)
 a(1415060803360)
 a(1411122969924)
 a(1405007141748)
 a(1366599922736)
 a(1400469532593)
 a(1410479071427)
 a(1417562387194)
 a(1391012051300)
 a(1420613434732)
 a(1414516699970)
 a(1440740738884)
 a(1392753866424)
 a(1403674463913)
 a(1403802629587)
 a(1401638515624)
 a(1408133383245)
 a(1415261479288)
 a(1404610404623)
 a(1444244644068)
 a(1390894011204)
 a(1402486462307)
 a(1414670570006)
 a(1413355278075)
 a(1397172588018)
 a(1400945571559)
 a(1402171730979)
 a(1395389276501)
 a(1427629250273)
 a(1418795130505)
 a(1443383173932)
 a(1385715799411)
 a(1440227053492)
 a(1387393763583)
 a(1420856248028)
 a(1400790017722)
 a(1406584065961)
 a(1432347166497)
 a(1408742844434)
 a(1396692295854)
 a(1427428725869)
 a(1415587609892)
 a(1407401433498)
 a(1403807493465)
 a(1428209018232)
 a(1411053092807)
 a(1418979395657)
 a(1420778861344)
 a(1408890958590)
 a(1445666338699)
 a(1392289262025)
 a(1453096285576)
 a(1414100001756)
 a(1420120594613)
 a(1411211669054)
 a(1416111620883)
 a(1426345284967)
 a(1445153340504)
 a(1428581488873)
 a(1419135138070)
 a(1454797051967)
 a(1412898900286)
 a(1435403117506)
 a(1449109361491)
 a(1448368183137)
 a(1426002916853)
 a(1428977250892)
 a(1445575259891)
 a(1458576475602)
 a(1436249049983)
 a(1453936644580)
 a(1471979901491)
 a(1466517823283)
 a(1440339848139)
 a(1440559252214)
 a(1435749509464)
 a(1435486569958)
 a(1452989354215)
 a(1459439620013)
 a(1447793805821)
 a(1424583020612)
 a(1460364701846)
 a(1421882716965)
 a(1445141521722)
 a(1430534811156)
 a(1427076488336)
 a(1449905666994)
 a(1464514585695)
 a(1460292980335)
 a(1432613839910)
 a(1438886393528)
 a(1436359243407)
 a(1438745345547)
 a(1451516832585)
 a(1446365512333)
 a(1477311387525)
 a(1463959393728)
 a(1460120344009)
 a(1460263453328)
 a(1443719775535)
 a(1426044933416)
 a(1433267371572)
 a(1456740570468)
 a(1436977455719)
 a(1449535118559)
 a(1459735109520)
 a(1458558847424)
 a(1477118187833)
 a(1453355684426)
 a(1468627837801)
 a(1464723436709)
 a(1467230607811)
 a(1450884414383)
 a(1448684758419)
 a(1438689781759)
 a(1463861245337)
 a(1450286865594)
 a(1446644882795)
 a(1458776081687)
 a(1474281157179)
 a(1462993433274)
 a(1439329238274)
 a(1472401338213)
 a(1475714906286)
 a(1463989773679)
 a(1473561948193)
 a(1467618308515)
 a(1472680998865)
 a(1480514415624)
 a(1460927131605)
 a(1466948772826)
 a(1480773041175)
 a(1464091342371)
 a(1487491027223)
 a(1441741959706)
 a(1455811463953)
 a(1488830478565)
 a(1469727140211)
 a(1464841778289)
 a(1475315495102)
 a(1442024083889)
 a(1475783417140)
 a(1466843233298)
 a(1471565867260)
 a(1488131707273)
 a(1477110133077)
 a(1460491639203)
 a(1495486926354)
 a(1429643463364)
 a(1437211258348)
 a(1470875043670)
 a(1481244360300)
 a(1484543935901)
 a(1470577390256)
 a(1504314599670)
 a(1514314237212)
 a(1470162610287)
 a(1457550658700)
 a(1484921854683)
 a(1479808935625)
 a(1483050852371)
 a(1495264739581)
 a(1482487525349)
 a(1492437165563)
 a(1480238728232)
 a(1470100249005)
 a(1495833817516)
 a(1464662779679)
 a(1486539074870)
 a(1502263393775)
 a(1495576294256)
 a(1492957403034)
 a(1485359863417)
 a(1472302825486)
 a(1501846352438)
 a(1491217849597)
 a(1482738051275)
 a(1489612952743)
 a(1504810124359)
 a(1510153648446)
 a(1487640578116)
 a(1512154900678)
 a(1507312538370)
 a(1482408578719)
 a(1519001252413)
 a(1498632715388)
 a(1492078985358)
 a(1477238651353)
 a(1500062338866)
 a(1502604057437)
 a(1501260656827)
 a(1487420090412)
 a(1478252382277)
 a(1500521165591)
 a(1455401459406)
 a(1491628756402)
 a(1526731712808)
 a(1500151346385)
 a(1490050340638)
 a(1485881650535)
 a(1505541550574)
 a(1490788743275)
 a(1505600266583)
 a(1497631584145)
 a(1493963899488)
 a(1510655848425)
 a(1498641958025)
 a(1508160545138)
 a(1504258150445)
 a(1498053773257)
 a(1514146203493)
 a(1532877730546)
 a(1495280773293)
 a(1499314713568)
 a(1503968531520)
 a(1533111942434)
 a(1528969066839)
 a(1499915338249)
 a(1533574821043)
 a(1513756378532)
 a(1505425318644)
 a(1507292891981)
 a(1497320299107)
 a(1506700251825)
 a(1516837730249)
 a(1500504744291)
 a(1522359351093)
 a(1538676980227)
 a(1535801269558)
 a(1518070901769)
 a(1516608403587)
 a(1533827092790)
 a(1499134284784)
 a(1530157998034)
 a(1515542110521)
 a(1519193562382)
 a(1514520888464)
 a(1524676736218)
 a(1506607853724)
 a(1513793575109)
 a(1493684976522)
 a(1514437410313)
 a(1513755529469)
 a(1503502021228)
 a(1495664597788)
 a(1537101910530)
 a(1536045350642)
 a(1520402471925)
 a(1503228457692)
 a(1545311224833)
 a(1512169490120)
 a(1500138024456)
 a(1534493559400)
 a(1519584408123)
 a(1509755042943)
 a(1532608470438)
 a(1522592373777)
 a(1502908276332)
 a(1513824801571)
 a(1526079645575)
 a(1532968368492)
 a(1528970728997)
 a(1515045882022)
 a(1528677348754)
 a(1529735810341)
 a(1499216446543)
 a(1530611209469)
 a(1535023088367)
 a(1543912886347)
 a(1522371300186)
 a(1520471297882)
 a(1537230944408)
 a(1553993814270)
 a(1544512144557)
 a(1529941686482)
 a(1535617511295)
 a(1561829454169)
 a(1524233292917)
 a(1553529163004)
 a(1552402432430)
 a(1563518022230)
 a(1520477456795)
 a(1529463154141)
 a(1581320911033)
 a(1532361914873)
 a(1532487613475)
 a(1529870114156)
 a(1544975921942)
 a(1530634207972)
 a(1555473666231)
 a(1551529488885)
 a(1567803336450)
 a(1541258175908)
 a(1543178921366)
 a(1536924535574)
 a(1577551824027)
 a(1532474539686)
 a(1549049438778)
 a(1534273115482)
 a(1553664488073)
 a(1548206318115)
 a(1537585185893)
 a(1568787935076)
 a(1530752208646)
 a(1538428782275)
 a(1562080978748)
 a(1566645921681)
 a(1585559850179)
 a(1576773766365)
 a(1557992663320)
 a(1559652741149)
 a(1553920471834)
 a(1570494411926)
 a(1552974826895)
 a(1584668764850)
 a(1578562963710)
 a(1550737824043)
 a(1531015619210)
 a(1565009773371)
 a(1574758872633)
 a(1549244130383)
 a(1565385843053)
 a(1549309866950)
 a(1555849192432)
 a(1562071136552)
 a(1565118385731)
 a(1545113354422)
 a(1574670980016)
 a(1553533374254)
 a(1596016530022)
 a(1590308649163)
 a(1582203343975)
 a(1560623130886)
 a(1564703547438)
 a(1554128349315)
 a(1557587012696)
 a(1555613138235)
 a(1575009276990)
 a(1578411870943)
 a(1584551237059)
 a(1561439470000)
 a(1571121886311)
 a(1546790822101)
 a(1556579913394)
 a(1565958303023)
 a(1609519165097)
 a(1569555526558)
 a(1545361834627)
 a(1565230196141)
 a(1581680861227)
 a(1587267325632)
 a(1560119373476)
 a(1591841431779)
 a(1571611234038)
 a(1578806601347)
 a(1569129559520)
 a(1580282394965)
 a(1559782154587)
 a(1598975488305)
 a(1581060191569)
 a(1564136622016)
 a(1579242689013)
 a(1549159409307)
 a(1584542893508)
 a(1590385307570)
 a(1556420455288)
 a(1587035284016)
 a(1594655609751)
 a(1604521348988)
 a(1601450539543)
 a(1580465205441)
 a(1591804297007)
 a(1572581904066)
 a(1566215430040)
 a(1584588534300)
 a(1590466704443)
 a(1575975626110)
 a(1606170806274)
 a(1592722414693)
 a(1609202100923)
 a(1584221032249)
 a(1557788808599)
 a(1558654219496)
 a(1576233739811)
 a(1626153678553)
 a(1568532868505)
 a(1592132522190)
 a(1618518900612)
 a(1592245404581)
 a(1564416376400)
 a(1607567649752)
 a(1609739757466)
 a(1577216547591)
 a(1617998708182)
 a(1595113165643)
 a(1588780190150)
 a(1584130899848)
 a(1599027990091)
 a(1588437235279)
 a(1594939662631)
 a(1575953573997)
 a(1585822664614)
 a(1604740521939)
 a(1595871356037)
 a(1617155395534)
 a(1612407905077)
 a(1624871508764)
 a(1606822405982)
 a(1617498388146)
 a(1616977089194)
 a(1602586229374)
 a(1580480062586)
 a(1608961378133)
 a(1592657813133)
 a(1617849687511)
 a(1628229828113)
 a(1617621174075)
 a(1590123023283)
 a(1610805338550)
 a(1580680867156)
 a(1600983192998)
 a(1614543241547)
 a(1623850941882)
 a(1587040722837)
 a(1598926014700)
 a(1613304986989)
 a(1624926299098)
 a(1596723827208)
 a(1609759102701)
 a(1605001430369)
 a(1590410223935)
 a(1592502179870)
 a(1602195100167)
 a(1625364332689)
 a(1647225454649)
 a(1600629116637)
 a(1628275650718)
 a(1618688774144)
 a(1633608952257)
 a(1643274180844)
 a(1636992378770)
 a(1638069146784)
 a(1610485076862)
 a(1618098866859)
 a(1602779541090)
 a(1617240426451)
 a(1624159708776)
 a(1627846050777)
 a(1625566771518)
 a(1607584438037)
 a(1610023154658)
 a(1619938981195)
 a(1590170956652)
 a(1610780113261)
 a(1639546045871)
 a(1601373014106)
 a(1643345828140)
 a(1632838689897)
 a(1600690242046)
 a(1610473593033)
 a(1623148209578)
 a(1636298018068)
 a(1637740666230)
 a(1634485022865)
 a(1619899627913)
 a(1624857360488)
 a(1611353309537)
 a(1644248278682)
 a(1620199538323)
 a(1684106816215)
 a(1630264589571)
 a(1654148897046)
 a(1631341324132)
 a(1634619929406)
 a(1637866428915)
 a(1641374510691)
 a(1627177557476)
 a(1647378681563)
 a(1622214674435)
 a(1641007903158)
 a(1618906816762)
 a(1638076836787)
 a(1613920562550)
 a(1681808314548)
 a(1632923723567)
 a(1636331208985)
 a(1654748844801)
 a(1634263471887)
 a(1642011147019)
 a(1659940106572)
 a(1638339035443)
 a(1654645512536)
 a(1629600342251)
 a(1623943134624)
 a(1655251671604)
 a(1647806979888)
 a(1648954838525)
 a(1614469971662)
 a(1638711978201)
 a(1663596517636)
 a(1654496751594)
 a(1671742806659)
 a(1659086668642)
 a(1663843054905)
 a(1641267721604)
 a(1665448130646)
 a(1649611941176)
 a(1692140418615)
 a(1644604403697)
 a(1629418013397)
 a(1649654891518)
 a(1655821644075)
 a(1675063048407)
 a(1653193490797)
 a(1652804100869)
 a(1642465268673)
 a(1666767618855)
 a(1659694355642)
 a(1657237379556)
 a(1666746449608)
 a(1675155317927)
 a(1659634671547)
 a(1672801868506)
 a(1679839890153)
 a(1644636321439)
 a(1660315967705)
 a(1664152821200)
 a(1650158042060)
 a(1630325082815)
 a(1669225360699)
 a(1643537744501)
 a(1673046786141)
 a(1667053068973)
 a(1640832147787)
 a(1672161224457)
 a(1650715179213)
 a(1657030377853)
 a(1665949311623)
 a(1666241629300)
 a(1687519922499)
 a(1649408344949)
 a(1686444080603)
 a(1654383844553)
 a(1657179631520)
 a(1637599795981)
 a(1656656014195)
 a(1676194240264)
 a(1715745328504)
 a(1687025709592)
 a(1695985498631)
 a(1691342476463)
 a(1675692830846)
 a(1678748261812)
 a(1698283428107)
 a(1656359544242)
 a(1671755773266)
 a(1688314925786)
 a(1673694310387)
 a(1686869292680)
 a(1667821604277)
 a(1705299396961)
 a(1696557643342)
 a(1668841154111)
 a(1684801577277)
 a(1682701385723)
 a(1685560774230)
 a(1648562587914)
 a(1707246911454)
 a(1659197713648)
 a(1700597390827)
 a(1691019515648)
 a(1703243405999)
 a(1692561821133)
 a(1672676563786)
 a(1706022541829)
 a(1666056948602)
 a(1685618520445)
 a(1694942710182)
 a(1674014714006)
 a(1685895968381)
 a(1689623148031)
 a(1719656628405)
 a(1692215035556)
 a(1703460755953)
 a(1682112419397)
 a(1696823280421)
 a(1660059432771)
 a(1674797425328)
 a(1714349902585)
 a(1674427882590)
 a(1686714175051)
 a(1698519320775)
 a(1709406659487)
 a(1709847493564)
 a(1701556961845)
 a(1714689482742)
 a(1697566171764)
 a(1706092670583)
 a(1676036257754)
 a(1686504907261)
 a(1699103606012)
 a(1690705045740)
 a(1713297912098)
 a(1699593488841)
 a(1689232978949)
 a(1678849722503)
 a(1717153249387)
 a(1723872378708)
 a(1718186568030)
 a(1726994056209)
 a(1694710256694)
 a(1691230678958)
 a(1732239964348)
 a(1703851224853)
 a(1706457493545)
 a(1724644496749)
 a(1701744797691)
 a(1699486150885)
 a(1698178412103)
 a(1748180483612)
 a(1674065895140)
 a(1714376194476)
 a(1715992140222)
 a(1720496655850)
 a(1746065647883)
 a(1725390426322)
 a(1737941584192)
 a(1726843353687)
 a(1716138505073)
 a(1714130710494)
 a(1730972077527)
 a(1707856338002)
 a(1719508990602)
 a(1717856341434)
 a(1702910095308)
 a(1724464764625)
 a(1729872914689)
 a(1723467025533)
 a(1738104959480)
 a(1694549330193)
 a(1730467682207)
 a(1681958513343)
 a(1702286979419)
 a(1712100306421)
 a(1744848045444)
 a(1748095183845)
 a(1697537189536)
 a(1731382035099)
 a(1720512926519)
 a(1736633804684)
 a(1700609877363)
 a(1745391260460)
 a(1736625842233)
 a(1707378314076)
 a(1737540156498)
 a(1733722619786)
 a(1732531069199)
 a(1705296960589)
 a(1738310447455)
 a(1739437937084)
 a(1709991616908)
 a(1761600165677)
 a(1732103998096)
 a(1722741954346)
 a(1697731913773)
 a(1721833110499)
 a(1707570431576)
 a(1756953420829)
 a(1730530691333)
 a(1745782976971)
 a(1752281239861)
 a(1710543014106)
 a(1733191083358)
 a(1739526821826)
 a(1729772198002)
 a(1712872645338)
 a(1744859022937)
 a(1763538665682)
 a(1744697681040)
 a(1724129188144)
 a(1763196066288)
 a(1748569858424)
 a(1760452500540)
 a(1750160620825)
 a(1756435276197)
 a(1722337602916)
 a(1741876446773)
 a(1756652566187)
 a(1730079086281)
 a(1756494671190)
 a(1740431968126)
 a(1749606678701)
 a(1733428995535)
 a(1703834558893)
 a(1726067209684)
 a(1711965305548)
 a(1398812679287)
 a(6123250)
 a(1)
 for _ in range(1501):
     a(0)


for iters in range(done,K):
    for i in reversed(range(iters+1)):
        coeff[i+1] += coeff[i]
        coeff[i]= coeff[i]*i%MOD




#print coeff
mod2inv = 500000004
pow2 = pow(2,N,MOD)
summa = 0
for i in range(len(coeff)):
    summa = (summa + coeff[i]*pow2)%MOD
    pow2 = (pow2*mod2inv*(N-i))%MOD

print(summa)