#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxlongint=2147483647; const int inf=1000000000; const int mod=inf+7; inline int ksm(int i,int j) { long long k=1,l=i; while(j) { if(j&1) k=l*k%mod; l=l*l%mod; j=j>>1; } return k; } const int a[5010]={1,442446914,669800699,573736832,439544520,478305480,20559094,909140230,435213557,814665911,986118548,595121107,672512662,67517689,388287926,874785672,202833329,257670328,579446937,673624912,447802778,409599413,787172644,840727125,279221852,768704242,46847131,643192208,590338165,714007260,763071818,803141285,844465606,232306908,71835319,373474156,25415358,843776856,8884646,30207132,37082378,224129283,309654210,708579194,497851225,530429576,689834617,789026760,286698596,184113242,426128641,358206887,588651854,717507630,469353289,15995211,187919841,600911210,220263730,277707279,676695698,756030071,79417353,703303342,250458055,247566245,567941146,497506847,137221221,349804277,109288211,236595759,201848175,328144056,330132174,16077331,879549052,495211048,214686850,423121829,136099022,799973294,987426006,848165983,429707867,137693900,933200666,934665042,835055511,608196293,367953646,459546359,190359880,158163191,726218574,735732708,799224320,961216857,775483134,21067980,523384792,571768153,481993176,194690942,141232855,504215945,845897112,100337070,937104411,752391991,584936491,939511765,703095878,427228265,145930310,969271949,385120130,218609220,220641033,892351358,147529815,459944578,713687011,705862481,343843173,539671824,768913287,664611863,28425028,985628610,463450698,665911102,877197082,699532005,302936242,793692277,238203125,422310351,274388211,608324976,841689037,735751537,428716027,984770907,643548959,176651758,888053975,372858570,983136056,362000274,705726707,377387659,202971042,556835518,114876450,264205676,341153680,180633577,3360232,845912223,931850093,576025255,62505638,342088628,895695440,249388344,246951137,269789536,450460060,757133141,808222217,250950183,302600474,297400616,424459803,60615651,702497279,114442785,637851000,950838780,487092554,36827238,689371310,133189950,460615769,659792560,880044929,423805430,697520019,727505198,452097685,806112977,336719235,829607392,933368334,136480686,442367621,701494797,664721621,891776705,737360819,68723900,413898937,889623228,985916669,649376355,775971537,429862154,615020876,219597229,509933082,532814487,493639226,581766313,373237480,250306573,642721068,799286909,521691728,897377082,790461864,550182039,583070933,922449687,511964955,610881496,664772500,889936733,665666493,734481860,13031317,471023761,663761027,98608923,581219101,837276976,247463227,218612646,941516561,798532536,576990631,692065251,944809627,578666168,376369414,513633365,695408926,661619875,15182011,1888907,924569855,295630757,48750127,509668496,269961808,137281578,554712746,62204576,573900563,487160627,596097339,408732055,939502098,470140435,484929054,37003017,955188102,303755020,135082951,830054150,775310527,525082992,577480438,122356191,992895151,447894665,807605185,809444498,808376853,161520775,349525354,726900582,50827526,877536381,728019433,450051891,66629832,145007918,479329904,17742373,683337168,231732137,499892228,432967106,148374755,926963644,290557181,614066432,562077959,1740731,823596314,870600201,312179598,132891132,902961703,604994360,952979688,823897231,528733566,784773143,518209211,338642170,500158464,819040026,492883460,781326573,285741143,976361497,736326816,571886998,655937862,351166689,28059562,584837861,473719124,236435568,304971572,143415183,927570093,566427236,930663993,50224884,14962988,316617315,367754172,346934738,342703820,391743062,79295667,324308873,906191941,777908209,135845579,145112698,625467732,991977941,367111295,211225149,671585863,516224356,346810746,592721035,12612319,292408270,867776549,66679203,510775247,580069105,115133635,531432371,252268741,192380234,533149887,453236518,769041916,590990485,746120252,653102769,712912446,848064973,893468736,230100799,890334867,500521001,905920203,695706348,453427866,359036072,333626213,21865946,464695312,643976697,579720839,512809691,190996735,895907139,569561205,334411644,463305490,547756964,423111306,404641061,264315064,242920532,314562806,735882307,227601224,966696310,162420083,804570188,488932674,507786524,355773442,134853316,109665717,608794600,834213211,348788584,497591676,805558482,437974535,667882769,855213391,475446786,314544241,173781152,691237263,302733911,430689299,943943606,553203115,858259434,358608835,545127400,323015593,740776420,942446868,625082245,160130038,927939405,845175520,970984693,378454008,929875231,406530932,527595910,582476733,753787849,730208833,132274266,908003079,94165099,70401050,815458168,764729675,256443960,416227415,733002384,275382737,617510691,366484640,112509314,294747356,790242632,341121485,312469537,514041399,841521366,963671844,83417085,726773713,637692911,227012294,463179281,633323952,167624107,800808489,647854321,406129327,77886646,41436503,56504410,670445444,391770444,454761026,308313887,407874243,429594938,679552435,902561411,245458195,407209187,868903643,826353771,189863319,722965211,360337620,632677876,590982760,393897204,396525070,525301729,746303833,768047335,262986664,901080139,783486249,450839308,104805911,493149062,766799106,367814099,318774872,592927301,102611239,820729886,689540631,749751399,905409270,652190583,984192569,374366450,923204457,89416781,699137292,885063442,801823341,366964355,767933999,67004709,309591402,788430555,624741523,724030428,258275057,391121073,144153687,783890018,841006808,233896618,60548455,58835337,644499457,582280768,764665230,147142338,113036634,702671968,232920445,878642674,281970645,568201787,879414461,50738212,482457494,418986225,494958702,245616189,363507151,211959737,702407282,413517661,697694814,763554751,695525960,141943646,396744767,395229624,388417098,295204054,960611250,559201136,979051745,999729174,564351748,951848779,859445913,214638497,758455283,696648922,920127899,553117542,158618582,191897245,357463284,835079591,66694408,199733973,815949489,850506708,91149989,249362600,831413763,33426107,105372786,650518706,780953380,748670852,286357474,281151606,932728220,70875039,833026712,60894396,85206120,258340562,141523740,766408914,858140136,700625136,902454866,595151942,142340130,789250751,36027656,640246702,964304584,439474968,289896831,108584767,718741114,737347394,220558887,203041425,214111471,933287907,267596040,23201766,920291816,439438365,594158496,82227559,263669608,826681494,586598718,612840159,248449012,350709657,57176241,280181983,467398163,5657202,729566514,104069980,310398535,58668841,572027546,562066315,814727513,830349453,270348034,88800865,220880603,648018488,620811111,416161042,744364516,668915749,169401824,666069940,828441968,460874861,351677411,331654141,779837822,130990825,157366912,775648458,354411348,437800036,745430644,39570338,172866408,718023706,780765048,423796810,921885262,668973602,148734621,215472881,971630764,837373209,789597000,614545769,824476427,805080680,967660453,175863736,581365633,184473660,585894075,148568350,411601334,796385292,541752704,653283221,852903969,296947347,399682690,509159397,896768748,152870111,364068005,286013866,982199750,864126259,226897151,312308659,37461612,140425370,294496453,74371457,536391754,513144209,946827414,953451505,439706706,61204584,280552213,277733382,656277831,568655739,947442539,25582955,815446019,702159253,335045979,40875097,983199057,403295316,380841706,300036241,203106437,84464985,169383516,930684233,513293770,59149179,216648295,243845767,21591159,293826103,481431952,607768856,811208761,339322836,161091689,108655800,415427820,844154813,819244474,253330561,706539614,270223650,747453510,88594687,819453109,861940017,499589435,544960867,183017798,143852968,765644595,281288024,14394522,643922270,88762485,755021888,74460735,385654281,811785866,327173552,635762536,263299043,844466139,640649008,780415515,936840594,985797627,752345050,530896176,603304059,355635154,440382529,698400300,963195317,225224491,623121571,351567867,433866795,394443173,393652882,649534388,793317564,15419926,723841795,167338755,207656421,243822238,948934414,417603480,290957926,253625332,284185835,986872989,507764963,626317055,257132562,84833589,148929178,808078757,516130224,744644406,109559577,619543882,895106635,467076903,827425009,313108059,416556346,417693640,575283504,159901260,860087958,279659198,119668195,384484474,853321567,87477832,511274377,775374220,893540122,838853714,60815526,438510305,284877042,818509909,983831202,545772822,150091348,971309702,979716612,261886637,147231726,310858700,844053835,872926232,110778607,803627046,514098753,36514280,249187202,31953394,458049347,607346244,26736747,148798052,824533298,559842642,111983816,279786620,770458969,390964467,734813255,845237372,988245592,528786345,978382429,385650405,649712822,356848933,436055737,484289738,94392441,208535216,848485131,622159000,14988486,862222623,177186479,157996722,842003227,131068382,810858734,748299032,730159703,782060641,990221555,191362654,401857028,411704972,251343254,85578666,773687553,559989282,791776013,922783354,240269781,169625425,111967865,119533748,983610589,706773704,654296619,853986533,472196014,864371301,96815655,290568888,525383793,815388840,694455914,823218535,645242468,814178287,881429182,234176808,800380257,319027455,684194202,946113492,141816184,579641834,891567246,119000086,288989152,997126093,939757558,385950671,144674460,894426803,595251170,900233423,803018219,494893426,494435425,995328755,525439198,109234042,730046954,786005245,427950797,945061327,145424660,709206982,249110218,676891713,981276915,199576406,223289659,51622075,990233388,775002955,214686502,49645437,216391919,113867207,305730366,909919712,342642479,509524823,199163904,195903333,129331678,39187958,639744374,279118968,881052028,710609120,896629400,765208404,950697406,911758690,18965423,641592316,69668586,827790491,914432044,756713653,150500423,787385885,987080361,361553260,606324899,986853339,791883529,637480799,193749058,122927475,9340136,210008290,333963504,706055681,529849233,273604965,987362163,408768567,880933635,313844804,253906027,522259116,276552476,701382827,478011690,68838648,669387157,128036343,478230475,539267362,342708719,950746871,215454649,933266419,693340989,377023358,135500108,75338654,671571217,131332569,816343601,420229260,126786599,34344887,883794495,691672888,874385550,290314123,717677356,366584665,77402781,398504570,253294289,523259772,370526135,912202886,351040149,198591347,935724138,123872046,656179226,640083423,501695931,775956503,907800595,76055391,320190448,839229312,726791935,681924096,412999424,715415375,787027253,599044091,915765391,928324867,423467583,757755149,157175533,907787765,490097117,895507303,685998882,476270162,141076779,213128576,723940800,233339381,842932931,123644686,200027033,98901893,385544707,149903577,419773825,38818384,688249728,490417385,47534251,183719390,917933073,507525051,133323226,907140512,878272803,727760764,34829959,676273043,418654806,935120900,20701076,476937660,622951568,718221814,713961272,923534841,61011729,915775822,261604045,914544288,367852418,43016635,739888265,603797853,250388381,323482944,549570161,922053176,821084440,138390898,197765287,533613870,498197936,694489679,834220999,47828719,803223739,294315211,630040804,11540871,788307812,380480891,856191496,552366675,672213910,630646223,904977706,177402816,185762667,334009561,775587403,416710467,643504088,165241496,625250973,820900135,383624652,268154641,726292376,559108892,601198476,587303925,788208179,43072480,914892148,262213496,570339019,452013158,530037522,816520797,690092220,60951016,651215063,172833777,142617347,730711285,859939565,741853610,135858220,209246844,552634158,885720417,751936875,601815086,50344880,499127984,975719124,234592786,917708203,165900553,324463314,391707324,510642859,790334758,399223470,224712458,536925994,597067492,851399957,15903467,263076063,684223950,381354155,549412204,35641008,733566987,798386455,869877791,347411663,47107183,202453007,246696135,32385354,819075840,785864894,575043285,320379249,30314013,892338801,366915178,796353267,484400971,863082121,895562551,650552203,132575807,116261084,128881161,861666119,288998842,206504094,712741368,63817008,975278555,634028196,831808062,242994227,802410110,253855086,274464908,858269132,694234963,659082951,130247242,334513112,558171622,106892335,639290733,847666902,706298800,917279516,999154972,401972251,356500926,730667580,279148776,320062460,984616996,83212395,530714122,824992257,641868887,710397071,23315144,451394074,729980315,831207992,400625457,493967011,96335445,620965723,302390560,417929464,881927055,459538915,589476486,107012236,447883953,395313891,350267626,830290579,809605888,593890461,979697042,595746442,255838494,434719605,436235590,34293368,885875204,529421466,185481788,830801458,263849462,507539404,952034027,986609738,90245576,816008216,102860942,936996458,753456812,946492188,455222735,247644857,890977118,909299802,37466154,538091416,465641079,487777139,224166192,957931368,661996265,475945247,826568637,34996744,635751849,598671191,367468264,810567910,715025075,9092041,193356778,737479226,697051360,843770483,751053469,387188379,519055414,286419010,543334381,900112153,743043713,185174456,227298962,754751271,479992002,995071898,811973889,204365157,417359494,721442485,516493426,197149702,522042203,706669956,991907414,674931866,75904103,480917401,691628353,999138520,691466177,215063674,676263949,597936676,502800305,576688512,201698677,749337165,677396153,722858466,216445511,44130716,551090153,326948198,451626367,392765988,874208418,888425366,66793779,462199949,468677739,39283218,604203352,416212816,508002180,489567759,848206915,905658658,774032446,691260786,495571137,181302034,128830079,662192713,339766957,715045553,74147998,450226046,383004095,912786492,769079772,459463795,560099644,880913937,726631720,153221721,274595724,434746759,23809939,513658527,737775975,346862730,717368075,995623456,961804522,474194800,484172034,36636321,104011214,529271462,780207350,321691940,10073668,288303809,385475140,261144788,722719795,93042349,10413377,94843644,671677123,577516900,34356885,885171195,83998006,258970723,786535460,87319878,10843429,739890581,447318143,330774713,828834863,820112860,379329905,686766367,754785662,92026010,715611759,836402776,409112436,142733040,215853201,312751621,669489022,217802618,484740494,616759162,382454959,268495741,806023258,113024063,36556280,256688151,468007570,907466518,745021906,862802542,790200655,457206836,505011382,558863604,485728115,482589569,478383404,140992512,991167614,755300954,823533963,433181661,849683220,996227591,856261046,653524840,924300123,395078219,947412367,381945505,870097145,76314634,230292837,633687029,497093343,89902339,832893426,328527742,468071346,279622281,832733910,458306135,535416647,590525796,34194954,167975490,766341182,695621445,239055347,990741973,284281659,208043636,20313604,373538407,504124215,170571629,74288595,60858054,224495530,208957418,275613384,33926873,190988638,485327776,703475222,827852945,305826349,424120931,732068219,819922553,135749328,175850519,406822913,178907155,560068197,806434667,245375655,444050768,433203407,818437687,364451572,146965124,585802213,528613918,142550534,901241714,556947627,548256976,642784587,25382562,927622696,990224995,318255861,598929933,21765372,614150010,456540078,873856622,211080711,992265697,75398923,378962469,770063468,910229415,767643373,361698579,740097057,1056257,664057489,545911968,227989608,49122107,269836614,877738224,321715232,244168154,496364262,719953480,163979830,701106189,777468323,581410469,838430215,904188584,136642353,71175119,501751024,261208378,139952787,959109278,838580065,883732659,144482074,843408348,257737187,513120877,605042196,391947239,717220689,407080286,986608348,613886703,497128117,463775401,335969982,198559190,54783904,854811573,695426498,757806496,394570832,378307225,375485016,772125593,739199971,603498923,477550696,795547497,511019153,609141679,965176906,726594043,482052423,14194724,813466772,122113578,977996041,547543779,721454531,254707183,18546447,73012826,727741972,221095270,77192291,297745781,515973230,608877194,388390703,972545068,651623546,571989033,541799654,587492746,463830156,470585668,296160605,848136572,840973693,639210188,540476407,925224164,348506684,671974559,910410760,466250937,287355937,91428212,495900060,34610558,153033902,574052304,792238413,778555426,146043169,623797615,10017948,392697370,523122855,706704510,871252945,358161973,387324442,653719668,129121991,266647051,600225781,172506173,148879611,537380020,947982926,779803975,76018669,203828562,924723614,92939294,898999418,922167065,762417863,816799557,670521477,369532581,549227436,327511295,649007434,310900977,920785667,595470617,235808510,317665234,482057318,321936876,769031068,557428610,391187980,148496938,909729322,618630097,369903021,283980979,750510552,335579703,704383235,185743092,819190652,956507517,746966535,368094197,409701602,847217271,958690583,918575435,241520574,584874795,12926635,254874487,181427634,103803398,268574560,25161537,997786493,801248754,215919144,603706456,562085293,558381389,724829279,790616093,337207854,187127740,755131641,509545783,699925461,751667695,724837507,842623345,621449277,542338212,29576482,60456949,243997274,708744219,531699380,423289296,666513777,821217266,280315778,271846927,428456139,322738736,908154557,767107186,824196949,316969236,61085463,73074036,575628254,530572686,620303065,168568160,829819569,905226366,731714740,249278988,256071886,615437957,293764925,719889072,692342457,310992817,540064496,662699123,790182954,94311524,810434136,665339841,943382491,926607798,128784939,711926368,800296418,699688963,154971454,648614096,723215415,288044015,945739787,582692511,18517874,807669117,122929069,501542715,723271713,447301123,544514387,151725139,227096700,605522821,729770476,370377420,168892436,645629896,882776548,25293866,650652611,598556837,863943517,978237529,116330982,371732542,792227710,889580553,604204889,444510432,126765384,740040996,421240318,449556208,75517538,26849020,792187530,468600632,881792760,580304026,797670042,604147034,536772160,359572686,913311567,527590408,911884407,691409024,634366068,189562001,264044837,727033377,452478309,230871746,294473221,242815245,148449868,513999467,956960380,148402644,789968920,249685087,602516910,419607342,51265947,520556584,625403034,69374820,232144163,238492320,566106240,363859711,381337661,265092390,474883721,832048263,951321978,200005017,115555048,320959695,3823512,313530623,671407054,424967482,146126225,539441475,675802310,69185757,937080687,572708773,437791866,782269154,558144817,964344429,587530296,579694391,615534957,564054609,224458142,143367242,8411157,62952180,342225460,107550194,701189268,518419980,340120668,513654501,995775773,797772473,567757387,136468344,619485887,129706790,897763615,345127964,409621451,291172918,310461347,657754397,483600970,853404954,839283456,769005720,122468871,333240720,641813076,271778369,217033576,295509310,712750530,799864645,357550313,614951712,438857745,111172843,92519357,785406808,762426548,679760410,961325716,470531801,68641056,864329155,901907808,453703967,530377463,935904453,936265920,571435951,839752883,100563868,773092276,396057107,26256644,494835495,65434829,416660594,126599283,400153490,660572140,323114404,861270588,343861061,756603486,936024008,63631900,529195420,561615322,714165984,835379065,424891354,911586822,754591883,698177493,338804062,778530054,412853196,801587614,477850628,521592586,614249285,784022006,989366263,563055512,655410283,703879392,769238181,750535947,731505632,294255025,898504667,490404652,637866141,624421490,385343825,235903479,826902620,532703010,68037325,764820249,973217334,898796340,126733355,11572819,54006158,679757052,663091743,526534095,411703731,563920033,674340138,995670658,274687283,288125183,162896301,771155864,342815643,39426386,888235589,973051731,256116485,458219719,764378517,97264230,489532599,806704438,474882909,762185118,57184857,166858511,299770206,650253865,691212854,9419573,997831137,29352929,48583044,524433806,957174031,567294291,357174657,861060185,44386760,368558900,335376032,601813972,42087271,442304011,703525397,22618380,863274284,316297882,972079132,934204916,269213833,955029527,225841490,821085970,79499850,923931387,254975292,643551589,184077203,625175380,263257598,828681711,962617600,595200589,394523461,98944157,353286003,955747343,162870374,444322563,924986394,423439619,401917021,343457386,988082611,385955134,749586124,911166770,308877587,947543775,588528992,51765085,80935947,178102689,626115279,370913944,860897301,511057781,879109740,582866293,856014750,367704570,440553302,285733975,572014018,377231411,642381434,744222001,216556168,777252681,344174431,84683639,552013651,569497283,143640078,648452075,946496115,561292694,377242364,830902830,787631664,183076806,243467636,549418744,953471064,231892343,254676097,272537452,114381620,719615978,580766408,481078830,274247759,793416694,560624697,462069261,852971641,249226452,707537513,476890299,210901319,387904346,957226897,853469064,41131874,703745484,404439690,260406763,690140155,394020812,547670661,995552425,763918435,964830031,108077473,739818642,71737667,976933559,438542706,352880780,154866529,919405287,69523805,850794331,560859086,771008289,141025581,414156506,125473666,84444886,104699154,975557595,397245221,887799021,70884022,334799046,525808857,215494798,209204542,97041315,508566488,311817912,191502573,98051587,834638224,838909818,197232830,33037923,605941879,803740420,424146430,102382126,328597015,625056014,110041733,708806464,542921990,891315788,196302209,833498486,309496451,670654425,291679033,866546190,333248425,405453494,71956620,304026833,799111405,300694414,612573736,972587946,721382553,660992089,344833539,46844621,877827060,39349939,578526565,921405300,263058652,916239445,474217230,809572768,292171241,801467299,386700422,971345415,77251613,331004479,781055009,65671906,548247427,346037931,234034603,504340449,442358323,31945022,528092767,936264197,394535428,341733765,416564489,882553086,396733444,754022262,881520307,677203061,927252396,868039402,531441030,868790582,393608826,38381984,192596227,636345076,525387827,815755890,181104191,118535031,723276349,628029182,610036348,140128651,404875162,945037394,141305402,750971869,575525934,715538054,165358887,617414442,45110966,307328802,817092441,718808825,705393220,816338272,79035173,231935418,272150792,269645722,345496010,426744115,791196320,802904795,772786832,834623924,281633413,247481434,923140164,694010307,952852811,220171272,635079713,544339314,506458873,522675605,188789126,806084387,683374050,291394294,929654104,576753657,802978469,760144018,100090108,332036428,772386947,531220264,202221130,852839058,565823857,664240279,615239393,649784634,775634204,757759154,21635486,745984843,883300672,33705710,632967647,21743010,437192983,795217716,49824168,703999596,266531867,571630529,274173181,346097409,70299423,515562346,603968598,947386454,720638356,700888320,381391124,384950448,335584452,900730293,762954799,135898978,24481124,587849978,956792855,879070314,587933906,735209289,668765389,785155685,918076288,149240527,830902144,283577322,144595335,289053200,641943228,198191873,793259444,58327002,566909769,139730973,219202952,188697369,755367320,979301938,859538162,161806093,713182773,949756764,116493002,973642414,584507148,335231618,220283313,212297403,424213191,372207572,146048055,87213938,159688812,824844118,508157501,97221455,636796453,788164731,776175783,805124440,254954771,19176470,74848746,462935850,315389946,298623943,51759689,636587535,413800808,217047447,611982156,936250131,320559879,553501142,312556759,263498238,542136457,551504284,896503669,880305394,176544219,325029599,485610779,260718045,881003103,142894643,859238670,608209960,80912772,209308894,521882675,839931228,132000773,519427417,993908774,102916509,37602121,674405150,454393617,310016390,340637289,400973205,744401585,248494219,768798293,900200012,943419300,207440213,852965835,589196373,32060688,353930561,224187442,963028392,583882811,301446682,336553495,39555911,215501966,823912837,978404002,615936839,735555870,899233178,78590037,884496512,757321022,280329969,130126441,475164031,856116536,207641115,467811005,179645814,703098901,974811459,868463482,613869267,980790331,835516848,793236970,35682513,954376847,117287129,497286658,550364193,647791282,189504695,660439383,783619280,845430908,561510626,627185759,26793424,100059148,113111999,803410500,960232317,120542366,104796267,6672561,324642507,807089597,289645898,635627182,974603379,873978918,921021522,309963692,778776442,168295720,93891437,211384655,859927811,907879472,963045083,484884991,949866332,727793985,418381262,401158007,553577953,982527504,923339998,895188420,612444348,649610949,127464865,326114603,301408866,890271875,957866935,568450134,466153707,596143715,632067680,781283890,996122693,783059923,740105054,431717986,378463596,485577704,426319940,964692245,937014554,592731618,428827016,956465210,927019370,319729057,556123493,964779860,580726691,619002168,351706538,245505808,336530747,170661160,922854934,257989384,874697474,882643618,372211692,423759484,584636656,504782140,505986186,460439245,73948684,674976714,73309394,861816679,22375125,715615500,657991497,667244287,30743725,210183209,957333018,524726300,772242011,212624651,508842457,978535839,323709183,78604722,945667252,608023119,147618258,815398924,876508220,724191024,282520112,972175476,164951434,672834924,721461494,475880017,159070513,982815558,682542754,720061248,841985130,293798196,572454174,583315770,852035876,985201484,399055316,657530478,672665073,292010498,617338475,273645193,132770115,179687840,766221766,159798688,868867559,96285931,872434107,169215944,148862948,476904138,199930576,318002045,36737739,507149387,654397483,302282405,443898315,433874213,950927170,386368194,809207772,735279472,420476502,548111906,75987385,963280634,332722449,244826354,797884535,911688272,434888360,774637843,858149667,186798132,320158714,137244930,923488701,296810210,411292789,765260274,764073225,670873687,685562657,382265596,893162303,89043662,495390194,809294687,490175925,512895193,586065871,891669114,627886801,100880351,684010761,191788185,648808057,246068026,192745632,792282246,11034942,170055895,872705785,374950874,962961291,19108310,580946291,526228109,143134556,27806397,931615111,185153916,211025949,17116976,805314353,530669728,792502478,951265943,92169085,592069335,305311464,786592205,517118378,872401993,96287615,814295982,238406303,152998674,571875137,601489412,75543187,513718204,413292257,308978810,816826388,595110962,867054966,140896372,206008347,667977627,682207298,673361661,886614056,655666540,873320311,833700569,656913999,597068362,243386061,357585920,591222742,171787112,46295866,732799650,301797817,717249454,506457094,144070686,997040861,873777001,462564575,42978394,825302126,736810196,676563384,224982183,235747775,458591239,152088841,139837808,588478306,359960734,356377925,644102657,226336822,761053013,342156626,719060266,22446506,298567148,905466982,345909886,954254534,384313746,110433959,71631295,534091026,373440101,162179140,88455680,143176274,168580217,630922336,810352630,143690529,768725035,669808247,809526793,656744426,636051035,731697324,893589310,684488469,467557507,303201431,382183292,228287959,30083642,534338863,398311102,76266684,560452256,778396160,164602750,393928319,201178154,600731913,36609394,258073853,714604635,102592972,845200268,395286020,797413716,792721796,789789674,480178534,898094756,293819622,710945933,563462915,937426346,904293955,547934996,827588736,235530393,836925013,291710806,814525139,788653430,750424186,582145406,970985953,260162854,684215432,876905315,329026182,20085265,861209853,679922869,730789344,36788527,575868651,164675821,768311434,269768370,671772049,519120647,818994890,95196102,973505960,704105213,932000636,103643167,166742618,210904437,492061800,23261958,875177004,432747625,162644115,260613765,859819178,388388767,144653563,155804783,12137823,584699470,614547031,536997522,422251776,343085356,818771794,64510180,766197428,904596257,654292876,938226172,266618332,669323492,173286070,996749177,956780325,159451744,344637151,979195737,439612223,153329515,467643078,36664558,924196339,180597473,65114384,117027929,541130951,305122363,872199383,558262898,325103275,282629564,868824939,801425128,327314858,200117032,932337319,907514145,170226454,96095963,169019505,611826541,635163640,823246039,489303106,601007171,485046847,288036423,628436047,906020197,109843853,743577568,68506913,103610751,982520660,269059533,655758770,573308217,578811086,458338180,648410410,276322871,123544366,135255960,598816051,318646677,409423046,213202989,854137946,168313652,54285462,33275060,71647790,652683584,562687826,845127282,791157722,193458055,91708739,189436512,925461304,712402028,928282127,675993890,40742570,849722007,479474878,492795610,265767106,595838706,456125295,905216448,775062812,32660895,536410572,156306942,11528796,715717938,190840730,814131481,490281669,915381364,784302000,351536247,682931236,348436388,451824987,872815751,331080388,273340957,450750831,27268757,324776050,338221633,831519040,758109730,400407550,306969261,638225275,585390918,324841267,679600019,164019094,861089657,794971579,979666964,640867005,570269797,660592464,396701316,890101835,977624001,809589589,384105289,941976499,8296594,873814728,13935270,968296260,984844607,140203822,445691225,440388140,605250519,569310556,856064908,776523374,368426909,21249320,738227277,761973033,324393801,176923587,556690075,981163498,957888976,888453613,276608299,251564353,314415659,518758378,575764137,149883611,399467719,321858238,786143356,3216924,577535988,239700800,469937892,281047728,793551108,628647116,839528397,199495816,96921151,863239905,260331925,650140104,507050465,327699112,129679334,63968620,906547894,927169723,759642101,719618997,630293162,722347405,543559580,599380822,230442601,755222042,950682088,734282932,539958110,456797769,38592036,215718392,645779718,814460764,696817461,912782584,423749223,173655424,440868120,198990269,146476715,798860443,820845402,543330070,810509855,955353918,398889395,860075426,145149392,543383182,335195889,811798948,896668096,561908386,798360924,320158811,533633152,952504959,995508367,751430771,876065996,408820560,229602802,300349900,2662705,748618938,768280495,758393405,150898342,559547479,964106007,838073719,743552673,794764328,752135808,589049547,789053724,620115946,724238750,109537573,995060524,225945935,513804056,115148029,901448448,56075223,836721877,726279079,619706795,756134698,180948322,9761020,315041798,126762697,597881358,629787376,50744674,453094108,829476687,387853002,96724814,163820495,894684007,880229726,726792459,972447478,986891433,57526724,234164717,668970041,286486734,787855492,189874148,144934351,891466734,231812166,104951302,802639734,153044739,111367815,669488307,325578030,492930279,934862891,933080105,346672827,402679580,582318161,266302980,22893294,704021476,822390997,258893972,515715992,133855638,433321242,802909690,78945466,345366837,445833157,556955663,337511660,626834186,143312764,537578474,215001582,632970285,416044804,263609651,196114378,182167946,74219546,211841548,550922156,975121090,734782897,724381435,16435869,322303645,193507716,338561622,106720733,793316595,75082448,349025658,584913805,67759136,38029193,709522301,897256046,319218849,860914791,667947940,382606166,332880080,422255507,568929079,835665631,158464384,674917660,631324242,825444216,778563080,402787897,773972767,333360661,332954338,907389261,721916170,638084920,429547795,94311680,573951819,231619757,641090666,536345209,453824216,261891398,93094884,370167616,427415302,44543397,453316542,242633770,138892687,481731378,762736485,77314582,560298999,196354994,418865638,93312127,329120583,865857565,348426407,173280911,425071029,734989307,369069970,611842787,839223501,73470419,876474266,243661987,923707471,202077045,158039929,464486870,990627002,194222933,272423917,491132522,60338313,193423634,737162289,767554394,413866833,376536729,47867622,915987694,762372377,712870212,709665178,187844665,690648718,748860482,120674188,646668474,18738128,58289402,724033925,616856594,322233295,938968420,459109125,379653415,453394904,521522020,988786647,884391754,274447317,395689134,431339895,798824633,719773578,662314917,173171412,738367825,582439643,918540104,285867726,677855880,566693488,155260723,437493961,331949738,887733055,1386248,321132693,73500329,744223537,851369876,539898376,432399855,238407719,620458901,889558635,273577201,113363388,194941845,923708731,326125571,74963391,498978023,363356608,427285279,243083259,438123291,372933263,117164308,967984947,837024755,126814100,214126561,641907356,523026628,824592917,57612435,130981084,615754261,1660203,103652839,226780406,444845403,616946624,849746038,132180688,311672803,858613957,929985054,588718624,513191233,778389408,662145634,589179659,366483249,363912421,702353668,228395079,113538217,651684625,964172143,416159936,479455794,381223824,252240444,793082074,579271621,336422632,23753416,533217597,552331123,180443065,344517997,156863609,40288400,477184333,245562165,345079194,743844844,677570699,786297736,230903151,876536234,986352932,166944529,23110614,470951102,814835935,278251580,966519369,619883512,795404352,466622419,226765829,236608458,727011869,890557504,164266101,187205245,369714076,988895315,899539445,305289761,880245037,756631579,875413221,380770840,410909982,211766965,622179544,566246249,871459780,696910835,280256498,67582787,639317479,836167949,846085120,901960833,745117923,533012409,976006747,411451931,681549549,613902604,840645555,749917775,886647558,377460338,407846840,461970629,510153266,123536504,114232974,668745717,362459794,325857664,2637711,326885952,741375833,443540106,996103,506359068,386405057,412400776,407981777,922228673,792883643,165643447,605544311,713764657,854763829,130747743,187853668,137049311,981744329,985484326,972667749,649061093,329672383,950954089,512585058,684380055,174089008,583740453,838021003,939147542,44061561,672263600,17047338,183170555,669895083,809034636,753615037,19828687,289251697,184775481,244026485,543982437,969489110,714098149,323151476,452647273,749069096,172754382,807503995,245249931,889709759,182281211,772659262,256943498,400626875,726284113,896276257,104062737,592896133,246684037,324841333,18833265,576251467,12780417,472646851,322751054,670402562,256651655,831967245,870979005,87016358,390070751,998201164,694165086,662142842,887344742,635785448,91884901,217303532,987404063,613861850,625186447,243136998,767293028,786897325,686668338,605736238,386267918,37974878,449821173,61457174,633583133,882254310,227704449,368830299,412432562,815734722,817370916,936363475,392273109,38618465,702940871,127740923,630331825,242836989,499745298,871428091,660172290,953329191,517404438,533581334,510347960,309076971,691597149,52936056,829441797,45803520,852521585,747121253,582150252,115003115,977491613,789663029,317243178,323300086,74468483,196581601,617320363,747179321,808753622,799877494,245992062,212387842,990184770,996929949,295723171,884324866,410400300,897772457,262195140,584431664,759464359,665057249,620765918,880962896,635318830,822554504,280610748,196464205,419512378,985383082,512251886,105485907,952209079,260472571,121538626,464850946,330315142,529102997,361647353,243626197,438426730,191023188,25052111,661177363,59555046,721687638,586263248,286210960,205151936,625849692,936094051,136010891,414419852,652700137,876447583,522056156,770627921,665692743,942595175,569133097,183592078,714793190,612456345,894627954,739656488,226227213,369903084,972753639,777260516,813494820,537391507,557394464,170095007,13402027,19805204,161127481,396426070,646972604,719321116,259878594,924132369,584316700,649994702,604236599,86287025,711950900,775339013,998252622,545871881,600906471,467725986,246749795,929763097,2156604,807523160,137632179,607109506,715990310,464763521,754859966,92200117,29688140,449550590,174741071,368367590,467076486,633640637,74656174,851556932,36539551,210920345,177569260,28913539,322244223,161414625,16839782,275379065,74295709,734169242,803895997,582052113,343788949,912951651,738266179,416771567,737748100,138023989,88841172,456956120,361352033,290727312,742342360,420673015,991428174,668827121,984151373,116142988,482396693,627990952,898888676,384878795,427253941,516361426,776912482,116712142,805676220,30857918,655890839,370890557,815774244,902326895,823223903,286316774,567814456,559014236,772754011,891397782,442606797,945109443,748906587,535376199,676801359,552095517,495411687,772141055,162880174,285237882,551597382,554524268,646324379,941785668,803186560,240992565,817206166,679073850,973030053,790823817,638486382,148447102,452223350,592506866,319890419,586524671,399832166,386037899,172776460,102887803,495896515,582731589,713999218,100424751,633969550,532414332,379829163,425984366,484123257,595365526,175446890,260939441,544870209,875107602,212350421,720968827,354827330,696804661,471636543,997693172,120682367,719096413,878389335,807091968,580995178,408789794,481296168,915944152,503751695,9852171,173813802,301348999,2590717,115809897,64030839,133589126,960674573,665868330,710451522,931300897,806852555,984489916,123159005,459973621,935570921,289364006,467223845,426164974,251070292,976779644,329706418,307840226,425479667,924082319,483015071,759720548,896911538,413051230,566197986,173613269,673516688,984613028,616061183,457114831,446498350,964618473,995640519,71113509,500445887,689844449,233089998,397691448,330542212,675507728,955200022,707732182,15468865,109633848,830354821,876205368,515364596,709935508,441405386,137275407,568863088,860859909,738368990,651612942,943976439,687966866,394674387,487852299,940411778,534049484,517876514,510072216,135373750,435265529,619694392,844959799,655218251,279937667,930790381,82442537,611424973,259972481,652565295,971257859,280857655,498380217,979002885,379161591,363133543,421209768,654723519,530317686,545504728,150241219,586780101,836327834,186426994,677934238,567194313,668506958,854039951,129355915,784892717,388178639,959618098,890604106,711388906,545803373,973205186,622086808,137695023,183727691,215189882,212112597,272816967,45340600,411225505,348494177,555392418,740848458,441258346,961099527,545125143,580614209,146738983,864211183,569035605,516773801,695648056,890745383,689142500,586848490,438437196,912911284,140671118,799302142,943100719,923226589,650309475,585009673,637502653,793145715,114656680,168246616,738027636,662766898,380006192,371472626,331510410,100318005,790448890,765923063,199860442,444634331,371239798,740007589,917272485,933074297,296678471,553615906,818326510,115621335,651418826,519166962,196619898,869373421,166453539,538436599,144795919,7012415,530743460,518773409,792647676,904701803,264593974,279170944,81119117,161013577,822844711,135892718,420248349,510535391,612690206,669259190,272700847,105930620,601831112,317529917,367965151,95311268,264674437,62095148,416793010,285505951,371233226,996047003,325102675,980799678,12744557,287311749,283555059,749895987,13480904,383252501,819068871,546306263,17886255,84839151,598501180,988680412,182151201,490422250,644102605,804670726,79853435,419825536,170320082,149330315,762824489,782810672,237463784,364650497,237599682,296497572,878576026,29345513,381784737,729878015,559422961,160847226,754822923,161992100,375879607,920965924,395323236,530920797,105676868,687157806,569919146,716256238,334661611,437445690,462310615,984171717,614379453,442552696,718109644,97755506,646480863,602806643,288603817,845557938,551981044,42925602,544013523,343533794,658069677,330621385,732199120,375598477,753278750,819521092,713757412,996054312,738201302,725707204,12284982,321281553,586814461,182090711,60010486,61295864,697409955,635921995,518663266,383252080,444342729,931474811,158938918,152315692,141013410,288298209,46579796,37684196,175831554,547975015,63893463,891291374,411909934,222303553,251347883,966761823,255532980,676194854,641087733,260498910,110074147,921180125,986800055,603342068,716217500,645188005,39615093,728530392,502022592,643565042,863833360,6613829,545558960,338416868,257534839,419329664,824108116,720789837,414333019,339871481,632482168,814979817,837469742,237214346,486645194,543514187,608115417,592255777,292814308,768295632,559590715,292890995,115846844,470590815,629727782,572557511,203019905,114445317,859274389,985325416,100563695,158413524,741740649,756917997,436216178,936011246,849182259,839227541,936562776,171079741,389411691,598669654,674452863,601998686,706494231,861140952,993449716,360527622,403567394,714226173,916560025,636106002,752965972,118821960,924854659,210058655,901508594,708365136,707466750,421140103,129289957,779525284,176551675,431177378,758723087,26432379,431277150,625656304,6448471,179448563,803412505,145351028,919716983,904014145,336744839,670577278,632028919,593900855,427726018,874172411,69127305,589014048,161404302,736322199,782675715,525110973,155875968,43006506,404009369,105699322,248512326,302278861,166122642,8016724,695566401,160770817,415096215,662329122,230378885,303543182,603717414,64201030,965612412,626426550,491045416,891244898,168182845,470390187,57429413,889979491,931800826,153624227,238142619,333916888,773836582,428793935,693173335,375826184,814204428,58790236,687474898,871417733,511971265,4126692,969927884,371526811,834528050,489049326,821159357,986221921,303302168,946189765,647414004,828021568,633727941,248425411,881787450,257290518,71223646,377625889,135829821,434503064,453992899,710238880,204400353,255568810,840897923,248811143,301566101,588435567,2779055,936978563,632214642,19756934,704102338,386277165,778643732,778102006,938870819,193802699,152112983,104031225,982970573,267274839,260881779,792637503,121597533,44834666,941022679,725483217,113962718,351909251,691786847,448422099,927824597,772320420,944078261,909452169,247811930,768709943,916965134,730739120,382564898,370413925,274597297,947740301,708604119,149893606,981479595,670589955,697416616,942968915,856599051,7159035,601193081,857333900,38210354,365701532,212974769,102214441,671551723,822996773,645249843,292422661,570031972,657497524,132426289,314774773,7262841,963448739,255968072,697032280,509170878,903593490,884355347,610402317,589116657,960321769,859982586,398453435,196779135,415535163,732733204,462657504,307440697,179516274,933944271,62574782,651080072,939360124,16246364,127872725,179889982,788028865,873009803,848249121,438793378,796378056,609575203,315831846,840349896,749832354,257949059,958382942,578408737,812765919,910118233,953650062,182793334,638996019,309483974,694881374,212883065,519052665,586839173,655903934,457029309,542483388,583269755,5658477,329562899,382336508,190704542,539137804,736994204,8176342,968582033,234875929,616599353,220418528,415522146,995063483,631197635,969290333,370165285,792777960,266988042,270142759,405946929,905465140,102462416,801628924,821146216,604224394,753311372,861432903,661142998,380605893,985930656,949622066,987330166,22033444,755307124,106782421,724298040,903294916,736237767,914539036,543431908,226718913,617983760,254630746,634207939,741427926,676476812,74630985,90542666,590004559,364229015,912105238,656218959,866156498,321942278,198207098,58841951,14842709,902504358,96810800,840635844,783907913,622034397,915908128,708642673,95547754,482670698,114484571,16984118,663181062,156115003,523556991,282703123,408329973,390429751,388210874,378039675,919713522,517507675,965451629,127516145,857978504,469196528,359238806,951175788,758337232,733458825,178451619,68638355,376219609,888524092,711834586,680727334,841731074,957712970,74892803,180963911,941548447,865206810,733250846,642199052,269032612,859894763,203947146,582531859,363099199,334767745,699302964,710849184,894480970,437233448,240817421,322149793,293348716,335769089,78530212,801706317,973795230,634155847,699215637,881536485,693988848,304122174,916064079,929054203,277094879,796670646,449657716,548740043,703496909,853003403,217314868,918332514,448754638,837271813,574506566,30673161,785096660,413137168,542222279,121236082,428304897,118595491,659039767,919601330,314964525,412394206,319562805,192395537,617443308,649919111,251110052,728646613,941549431,958330777,86244352,832702400,340636312,685775804,705010738,100634564,620053342,347451567,727546712,330709728,258555573,198376374,217028848,115739144,431271554,370049093,855966511,575640990,641899021,296832873,20400865,186870659,725537960,621013318,879671192,430888414,438916350,461952808,7693350,370863716,356280699,746879557,734827386,990945183,248062394,983270362,605399384,68251412,700180538,139004707,579864545,169115446,13714981,20898168,265207748,204078350,969392609,679634304,52639670,555297995,852758243,423315890,336767369,525733928,770391016,247076450,239168676,750376788,961677853,840186372,879967673,104578587,930228536,666308630,469128081,29729766,484365497,230728643,648650922,388247463,234332580,685517086,610773830,228551727,254679650,199979259,922885262,230891146,391706502,54641855,575857473,885761057,696185381,234290408,143449098,188786778,737697442,341992,35697708,953427468,306865929,21457768,607888186,772176641,59433682,628595662,877282514,983452499,741942978,853437151,759980645,748255545,491469852,635682661,401608993,528643336,66582077,441394836,856663256,141901311,652279372,560458889,778693186,579958644,73457875,996145051,840896113,730272423,21528327,676735203,526461524,875738597,746697451,713423692,303966898,577087658,393104496,783447148,504835261,592590724,607941262,649852448,143790472,722206499,701183294,432817722,507897032,863632699,376269033,778193277,86973853,189572215,315821489,78419330,554284272,863095981,499423869,185075902,255643366,106393153,675056082,655951144,443600778,725738277,705109135,447610724,47843464,210722595,418448055,104823782,684422264,573062842,428695606,452385478,490885286,709456234,15507264,89859164,364866373,34036281,871076700,653582395,713960694,711447102,731722760,993089086,669246190,331351426,956816069,934871988,605240391,483417178,7739177,921616173,534456378,590743029,841314742,39528185,407248278,254601906,802284703,233173051,944875857,264532909,921443939,714671094,52549109,173972851,570591573,498736179,773604136,49427125,29714476,596211939,602076829,29695911,802950939,110537789,812038285,112564005,967067622,440479272,974658706,404468857,753392078,799100638,655989586,674967541,891301601,483316995,270249297,674735127,803868447,798955968,546780922,598414815,21841561,278498669,486865118,530758027,515528008,174294299,223364553,885080457,850691974,667813543,656801844,902535141,220975352,397961232,822937122,883026544,795049960,461663954,665694440,160007889,22417907,863682667,183737675,412033706,641510860,263349992,845297252,630705237,430488415,379150986,612012511,697107471,639595555,357644150,642720399,901093131,299186996,218301680,157340484,260178531,785525747,198202548,553645618,69302075,287189491,818389036,662149321,839894850,816580465,687505970,510590867,313247235,271867020,448964962,69236541,464781313,761355241,652139528,398265796,525282586,607533699,228973115,979265650,849471800,3878954,800336196,630677075,454301551,44030885,290502858,265157362,800382862,555207633,500068608,507707144,526157386,630768790,425798243,535484399,5960976,990892916,249432282,679786117,345100708,783661250,124756375,553952887,356613071,382957044,221831026,391616773,230906433,616352675,864727571,657845227,548894351,964010657,874781449,28540413,346678685,504678305,598174509,714406032,679186315,314540955,647818668,684276060,526761942,641006732,566561236,170229648,770667058,2518394,594154231,700056131,842348020,213401022,562726668,288980400,675431906,426322511,669785658,248170595,74007813,495894624,726297605,287626546,654582312,513617547,642089995,200654705,869432562,736983959,581178023,619036063,119609654,848131314,174038262,749989308,334705353,481779557,394279272,54491313,540618258,463549488,256085227,266397044,257001441,283347004,230092558,751170150,938580806,870291635,870248367,157523337,75657365,637430502,86458777,158545295,79399260,346637511,147948126,415728049,410477821,625111751,431977135,6325481,449000524,509477079,290051437,899106764,589726123,807153116,491275172,509674122,384883319,87756461,844009735,482243694,214999444,959560933,471650671,662923257,363754097,96110231,1986636,920297300,326077913,169630395,557534678,16387025,663647984,637532638,868272812,939582448,280475279,223857396,480255442,955405167,368567613,773033698,582989395,416247318,479412259,878576611,528763748,155169289,176305482,689606006,325414871,994211170,472077428,364137446,789143056,14281522,359421146,690546221,386048887,609503217,179041574,885476750,851274018,871257177,485707386,802176051,261691227,620097403,429399342,261625516,373822082,650869808,840440954,22481236,456138629,752954686,275332636,645096535,540741062,884655017,459783110,954847785,486720551,984767913,417344350,586433235,581112484,126020478,70297797,915660914,897509966,276145008,85028859,521596912,381987270,378340339,359804966,196802475,134430436,662389783,721452261,461932086,708065472,279126893,939289868,641165857,162057796,125745960,301661649,298418222,57647655,413682677,457833080,964237448,228716792,799566235,296415288,245056210,217722184,922665450,250786802,244563656,487519925,184189189,679158732,350135976,826114466,617017842,225625123,954391160,137811395,255779075,480986767,930023312,380543362,267656976,6440903,451720386,677759706,616414908,293336257,718700071,977129928,133455276,465744393,380295028,253065443,861715170,216132513,861385481,998242950,285414032,776895780,317005442,469979156,750569082,855611545,744060800,961017563,897175783,826246862,18225630,232504226,701447128,183738204,915871213,343151725,149155379,305564248,244182928,293515464,908456552,378302484,363128187,105923532,159235213,423225461,821906589,687674288,420316439,777287007,766735334,460904718,107363361,922898939,194520531,537361040,518387448,331474503,255031629,640238500,275234631,679707088,193124922,959773931,508289818,283313086,709777837}; char s[100010]; int main() { int T; cin>>T; while(T--) { int t1; scanf("%d%s",&t1,s); if(t1%2!=0||t1