#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)    for (int i(a); i <= (b); ++i)
#define dec(i, a, b)    for (int i(a); i >= (b); --i)


typedef long long LL;

const LL mod = 1e9 + 7;

const LL fac[8020] = {1, 858567700,4347837,671842248,656871685,338476686,549441636,170385670,464424990,905649728,492477743,546067626,14280205,808391914,572137362,987992862,648866010,833410387,367751749,868521900,824767231,957328876,675376215,105441090,779892377,606426848,791318754,735177082,225349011,861896099,277931935,788826587,435604553,806357051,306986493,282261462,273113907,827509821,445957196,106358664,277391801,800925085,431012599,374236002,949941200,219568874,178232881,770872653,870152548,195618825,248270948,219162867,875722956,160251545,162331436,153785239,567552099,431225381,749785252,466288182,834148563,533137819,32932676,122736855,131039336,329038106,653546522,169840731,694182922,981020740,183556301,679755441,974026543,874412948,348200463,257545683,838775504,146122986,661632550,145172190,401503328,37233527,883517648,2608197,667314564,788475714,412226621,581681543,930950255,741332165,600733796,877372408,188626608,282173246,711365715,937065551,704816096,977157026,65876198,292425161,812847554,641655315,904365309,479958320,746410553,167202690,903223909,771414165,710805179,624080613,243664140,291115042,715513843,28346368,186845514,188203341,477219936,932182994,840781915,634568072,258587460,545333535,980140842,553411033,702404749,269367681,944012250,583485378,486940447,507062205,566571502,228097303,145388557,685099579,224903304,748493592,397036162,378803964,968015781,148921595,585881680,416631164,75529056,621243957,17089167,289749984,670397866,653094630,278247194,588239885,535280817,101776222,913154115,480635908,231700224,222911341,598490892,93251724,641692987,517045684,557601355,955951308,224977884,133595834,190487733,83664005,308847657,538451915,435627314,290825451,807541903,896817361,846329914,410425419,338333489,908186615,647113028,971257777,261264349,147268599,175702328,892963386,865871118,72401844,150165973,563570704,423935037,779810967,947047823,663156319,3411487,196978960,123477484,924393443,748662290,429606447,435381307,149102469,737741614,651749461,759160471,865815303,84143086,546790478,636383528,434417452,602570521,583747849,29999162,170040196,363097845,587547826,980355145,331626206,366146167,741100830,983312905,930977581,708554026,272795084,753730709,52183224,328278089,845016961,363906246,546621044,107023931,29375307,531791069,622631721,444270885,224175287,365017221,945123664,654279036,198059701,284044625,943394924,900173701,745134376,417648866,902973949,438210805,240536399,451392136,877256481,30486890,440076648,944102207,265105681,293543262,458817732,751211951,936161850,390423597,301358737,469690133,967786138,313121411,170363144,738221137,920924200,353400006,513015330,145459698,111088244,910758913,873223192,132415186,827992551,850241544,129112891,76545088,198315170,24339765,554663868,712826683,806510399,976062446,998365466,191703729,622852362,816130774,40689787,737518661,49176295,573991072,766830081,795865954,326050691,583734353,668188370,193138547,412207791,660341515,462583400,672810504,717062938,703061125,669744578,904067634,8609015,880416708,359372595,694772892,768631370,894234188,322761904,724348448,550007452,311232317,541761850,356758524,82717970,241361832,62057285,310589278,279809521,103631420,766432195,259422068,916504822,555387161,233579159,992192489,115365492,365831939,20155310,989097630,943386352,242709769,660664456,890557053,381932224,3759391,747406265,211915555,986860141,370630274,951386854,601557731,845648478,798400066,299903216,630440978,324364453,40473336,767071078,239412968,763718795,29288360,923554411,291471957,213643752,776227254,637902229,661565195,365308831,887947468,596481798,129488428,240032594,405378884,57001733,124571405,851192824,388503612,194741866,942576429,777712461,206539162,1248457,646829272,382748908,294955095,870360702,969692606,593632077,951321511,786862493,447685839,590535200,531489955,60455878,353752299,413444967,630190239,963585849,308277256,103129760,668572132,290823377,251434801,158339345,670988873,342662351,144620498,246761626,116814658,177831674,265545856,606385571,261762686,650022531,664537812,345790383,665723300,355705350,91334908,320252514,544530820,514185719,724006459,596458468,203330383,433456906,493818651,923120436,647669848,182632626,217366867,800457878,343345161,676411232,906403061,633951884,620869775,213866521,992138650,100619909,187260748,186527774,685953293,817344783,719173726,424835658,617528897,533072163,205128612,62638703,275596702,512282788,646257573,887746669,952100431,638133817,828653929,774383011,708753452,511208614,248836259,67496759,346876061,27047646,120136399,7620610,291418168,205104811,376327299,597261071,633569946,653209437,355818576,405473194,448802227,989773455,571578107,625304042,734673742,624812901,702217139,378919184,104887757,169248840,592823268,197263271,86467793,328414479,61758421,678367043,473354595,509891237,898216689,263200102,306035437,88600874,215270916,103278278,895194520,366027290,860210171,688152047,383470510,108115650,46381042,979772818,953908708,873530312,411908175,562298643,520330149,955978590,718268953,868439447,181520268,142885083,111898932,904982449,391582569,820494185,348928503,626049051,204825882,585258333,78503962,440149287,604675398,769446339,437532239,870106894,358882725,115706971,481860398,685992273,884815997,580019927,879489905,372388737,892657028,750698263,77931712,922061226,37800669,213311982,469085900,693576628,400499676,899188563,214265060,148811380,210062913,765711143,655335575,31534004,907345772,412081103,666308770,648853939,635990617,382246938,667403314,159806356,773373787,914166770,52066423,258833996,751459850,403224735,772698706,243345124,732918342,822845190,638153257,252056026,519732116,116371925,688352671,509666068,173579632,498739056,649947910,243872724,830898290,306088305,744712550,338195511,621030918,607506357,496234663,736579276,301249936,980553172,207570952,213698859,235765830,418120706,164660871,398993062,838461931,354125944,11418265,796192132,674349323,928262016,861318618,572214016,572225983,464648351,252211299,310431779,324415279,270533349,790580096,558857724,321477967,23838948,302832760,69086298,542665810,454846137,113033773,689509580,433036925,696793888,278106650,729928642,10468942,806158529,543072816,442353964,73003376,991962817,424739452,512011341,612447285,575405343,448928488,628548681,966114802,821220891,130773893,140443908,61902652,555275368,806985775,88750519,675414354,617116489,509426299,10748161,651915544,53054931,456372510,351242060,525434037,380176560,227574513,787766799,975295311,254275976,265058808,366885499,849342615,435110011,299867115,445213385,309506207,450437887,117011382,183163446,839425516,755776135,958747517,630523306,37150595,359212657,70259028,808939133,28140689,174666836,521097996,235079159,958966724,171514900,739079974,844335479,541964177,153919845,8855227,258202348,94191363,240436722,222091781,296781474,131847551,252727417,206558595,310653286,808371467,870805763,849939662,455280640,780865358,166824721,314036991,841741563,650910649,766929862,72873874,29783624,47046380,785355403,530809026,271615745,26523144,381839698,3837826,76797146,611987636,292961598,730947295,589287430,968755441,637777937,353967159,341130600,377192362,800697903,745765582,239123569,590662506,636805786,346490884,78409104,395627324,563473484,632337230,460451607,564752253,984789844,113105798,323803873,2525284,777311761,864354992,611335347,712514564,764042587,95670209,677807082,833755237,184258822,214206416,280914508,316989283,539779674,350532910,512462804,633179576,237580616,139358050,214984973,759365738,389049111,751051881,244577226,781544550,939948466,852042487,622854895,629680309,988170593,648227449,951948132,419898873,978889020,87424264,355132235,260900624,58116323,345070485,569514120,900879314,334387825,638377855,791733317,588425650,69497890,891759780,959941000,202712710,90736085,292228693,660824953,920338942,384680106,992402983,8167186,706901946,361926591,444404319,702381901,644229809,172634214,214964288,671808163,33917257,519015751,560782091,953023750,5767475,593484976,996932072,224679754,611800591,755030434,629177375,488283903,538628410,14125001,354768528,801841925,814822415,153819225,978038396,832052793,296047479,68763140,739107655,101967336,480978870,771852384,768352893,316842867,550503330,164223316,535920496,101329305,179412773,71529776,538848024,281772532,987197610,660975005,901815616,648639084,289769573,838281791,409182039,770607663,779196668,33928762,73310803,631482803,96208475,456667828,232617454,652736685,654211654,457004058,928221811,158198240,786191543,992429717,751970205,762109475,528211385,954658650,510602301,116057525,211817499,149573368,796728574,427458054,235842276,834773717,103055895,186274657,326801454,520835745,227495627,776712760,347474395,729231025,100595582,981530236,492982582,373648793,325425485,35456505,99918589,714589987,714576197,282982715,866551191,605870824,728295088,481748871,619118847,168965466,804026021,526120378,860244677,550022911,841419933,141633904,12744375,998307270,528691576,909600301,355974055,394685670,568630383,149114287,418229609,619219086,82384189,328748626,968694975,468430588,308817542,220812570,737545355,562339970,987848971,33345186,754154769,871425109,951982982,652703844,966719249,466349122,352739055,980724802,93572141,702913085,460329503,313532220,668862625,310053448,817454321,74557720,253553766,821623134,345202742,463788706,34892656,873404062,90314057,454345528,749764848,450774205,616409994,871626126,752797832,989937252,199260455,719338486,873929434,655002059,523907707,927914084,218801128,556217801,257131991,552092012,568483319,991581236,571412432,922459537,884789446,783867171,361635920,365670542,632538438,627108329,314003284,662083892,106490375,396487601,2923728,134350793,892779154,221911735,858450042,417340256,459172393,341140735,48275047,652636546,437987213,955501638,697938392,561358045,709213418,480913403,776149846,649142690,66101103,196957517,428786780,476255000,255021825,351427943,539595028,394820099,790343014,643185490,905304366,650916298,650490223,707223977,335963718,782987741,829502369,189145523,213978915,11799498,816631225,938707150,126031768,132058473,438145812,73071011,257677112,234500963,828032743,881227714,4019899,410407510,136761677,886213158,687233009,337676920,624141066,438495445,730144706,446196570,401085110,473129363,917371608,578446370,147523039,305543331,665589134,872199746,401538066,700752002,62051286,338081981,881711123,985768358,155408381,215943512,689379031,761831549,162242971,690162432,72928047,774460940,949750297,935124029,749572250,95898525,808441904,396249399,272342163,553288922,841890784,636888991,679423115,494160220,872493163,932169345,868541193,234790241,300427397,720636090,100866835,707919333,409302099,157920495,912244971,212877234,372002113,803664376,501873904,224951283,123724860,858181130,234613237,97418355,157930525,445138328,33184110,469317708,213272817,411425889,280348797,145066627,452931902,993755940,51391294,140523599,850889997,328904092,946287520,2681512,752520895,83415282,649017215,71013431,313966820,940294626,4389983,727629115,428825718,761372082,123595849,829132513,171633643,250974181,692196078,250281467,837835556,382224021,655592367,68118950,27026894,758454465,80029441,191188684,455701632,375439977,532228021,740185993,589972571,686571079,321919276,310703719,291204513,448184536,171000327,106220201,998790086,717719248,237478244,369007875,54946399,51647103,49731111,199759628,597437585,58297075,918762226,286643360,883374997,826157005,119071864,297882209,431488185,255909117,248025199,728441255,281665065,332630597,449017373,692001356,559036657,268785732,886050620,896926112,430877432,618916388,657412741,776910644,854757652,418412777,979051365,342708661,869377786,952581048,629697388,962846103,475394805,448628873,865641832,943669193,892903148,987090666,525870679,341942572,706337098,124928258,125155355,499112374,701592453,186425758,828047845,555649188,14702190,198357159,395140781,847423820,987585367,729143317,748165921,496377194,806034928,582797207,29018049,811623209,589627359,345732636,131387277,493297520,3056391,487091498,393743787,389918965,465081949,549427401,35886816,989928665,664471182,761166512,307137314,433891175,618857919,715777820,378519538,565580076,105485,72423274,178426715,967446111,995188071,394849793,515558182,53261713,189904650,285046771,365024755,3537103,715977988,764895184,214431868,464754049,227489147,549932335,278292627,356265355,651802868,903874414,722607517,870125335,571676900,631413266,387989736,444268041,397112719,100873957,626844902,505915453,227544600,288212028,393183144,607259014,425075967,195097905,95696132,455679150,766312716,940991060,733420947,554326420,957361979,3725249,850650880,564849458,654180048,785092231,506757893,95912823,681859225,88395708,201172889,264020269,104488166,544737190,209818793,260787540,182517740,684925664,22415396,905694924,394350928,188770472,54327117,588118219,267674227,358723166,995370547,810878864,249617206,630561574,828512349,511732908,683070090,340276225,538559672,51758765,703492433,91473028,519417220,270733661,4038458,196705853,952955078,123576697,216754269,928175739,422604225,161167392,679618431,327367240,856604420,813186035,710324778,566244964,227934352,965462379,144055766,622792009,378040207,408894258,665950470,691171864,457611242,777617181,608510836,971582144,60650505,235029452,632981430,644814523,406386697,858339367,696797678,105087115,947687312,530683023,216399652,928491752,409912458,439545929,441400131,590587220,6905544,219076958,491260308,28519503,903884906,215523625,124684657,355322789,724136606,362565974,266373599,957301375,275634299,570718443,751054798,531647666,24510359,101616107,530153217,277699444,938234303,74856415,995896187,185826107,133133861,229034174,582971196,211294840,860959357,135937277,197729831,254230193,109664592,859892479,656631731,150533764,760014307,498120890,403904793,19988793,981457806,919621259,30518622,134156257,855783379,776801304,778079250,110104289,144097572,610795295,271153946,552216928,219233986,261359693,232826524,632449245,900737165,736595055,317436436,768050094,927982859,149565393,521250479,509814698,758352600,996732233,997495819,711232111,399595645,168350773,80459604,835384515,786531437,973836704,910360459,932706416,504502632,651719689,65995959,356162025,59847226,197721759,38413187,630557182,701223588,486176557,676133993,271461501,867529412,887446815,319387964,316779845,417036456,512368871,698172469,171674409,927480266,249488664,54291034,359525432,40585493,248251315,742804913,729575250,857012361,709583113,359737475,125463793,335204117,562107969,929680538,40152292,596416344,905498748,366288558,315364248,156485270,400068812,702653922,296995576,31418724,200241402,637570199,815593756,867862943,545580923,288584729,925809498,964727882,992824736,737095271,855328085,643703621,780860221,947448634,660137937,293116037,744921676,697697211,595730179,52572463,732409050,603085182,411904421,683206622,820209523,134386200,448967027,571782123,736044703,942040517,102717012,246026972,555931348,963398504,396214746,922678922,602746767,358673025,472566463,39013290,271519963,758125141,553161238,759444453,767609503,570813294,302861345,6665354,973580642,811702899,606565816,507234674,26320241,436058459,187504424,53924934,19937466,17027358,810666151,164560929,35485087,541811684,914159620,456845679,615274472,402452945,265843398,604754759,280512837,174062343,875527689,701527777,75408668,302301132,951083801,498704261,389035127,243242145,91783656,760254122,481020657,364955719,382755816,452470127,172603911,178932765,13120740,849763877,198761722,450202716,817636457,291919029,256655927,309909745,803224947,792317566,992571272,254611521,641605122,923134003,157462889,904372589,286320836,561325604,59437785,716337868,436534765,842293403,878512941,375481968,159540496,510546238,983733136,109278381,889648717,125243426,266457527,634815914,7365189,812805605,104491720,987637961,567899177,527722409,684966944,664179469,230372675,98292134,839293005,775248892,174942314,431939334,258372449,134666113,94059712,49897106,628025843,844022820,673189514,408000328,18180628,602633537,313718426,718128771,738092244,147363004,725037498,900283643,309829786,473600067,879480298,158425345,653976910,284764959,490249960,65438681,354342550,782449336,942741571,860239421,620523377,963288885,843626715,712495272,142832155,457782016,372589210,248532101,197719680,882419299,561605994,740523067,387954417,65816737,146964015,979648729,576988210,836035655,4122373,401918148,371454521,90718478,737419909,655494756,929461710,250268602,279855876,770794719,763429230,192111551,759782349,552253002,926066641,224117535,633028794,964953899,72130349,133947015,916538365,904805012,733169778,275195962,327875495,770605771,434044922,144999241,842379546,74603327,29078851,114915332,810504990,794531951,682288738,649422209,648385733,149732394,759870113,141788273,836332477,141303760,184758022,790535122,499425351,516663233,282588943,775563422,241115215,931406538,680459851,328780865,10319528,779716724,549045569,320782685,113126208,708078153,708156429,170526589,895301002,830554508,76529471,518211485,636044122,20621949,747580138,211234435,751512278,368446077,852546579,246236897,973997972,948578989,709588850,606530021,909855138,768401402,95297046,265129979,141830321,813657474,724730977,746676637,860959073,74367800,934466440,33433551,96004204,289144794,940079748,314910162,345973427,615247904,704166800,240402349,299016959,782739489,156145110,987295947,502949226,295008924,382768090,831352528,484764398,109887636,158363559,664238192,634004677,822266726,884414772,688660811,616131260,741583859,203759933,494917321,343329663,268648556,861723205,282457816,174252167,722179516,155600166,623813182,409449286,942269395,663196773,294194789,868483153,367021008,662339415,622706386,353850822,275529046,28255907,878096710,625444760,810539903,472328727,467018807,869514978,16219958,638362168,174876760,54629791,613986528,560558213,70849223,53292235,822801100,76880449,635113726,708753290,990167801,741155998,319033983,833855295,191517527,849378279,104521493,197587559,53945223,602736200,252698059,818144941,654112592,816077304,223386031,888606092,108539694,819453308,385766279,501914073,714495483,660351814,300284759,642277464,966295841,818979204,790203468,658995957,399513263,555487540,20922734,37383152,369775017,958645747,823798032,755019151,900979907,548065546,793471381,896235729,485337366,803616617,195444593,773830119,358049555,736274924,553312302,204189523,367535092,567260162,186295578,154844688,602750296,198526463,640114334,370104078,630687956,902536210,285842035,844900427,404891078,647120893,681144710,245742242,395712883,849780019,814457412,430453960,339221388,564365893,389334389,653896628,683874195,877331226,225455935,462088035,831064500,684805215,655591819,75198348,728538779,666715617,812171931,869910418,609307698,255406743,794909601,123867820,273882853,272810462,326015890,790338181,403628372,245711316,370403727,828212253,745172554,753498778,227697496,172071597,27159794,378422426,773503205,807148317,423025818,335343720,434239520,168684366,474627143,818234826,7979561,101806488,426101165,635511779,352089027,243274241,569093216,893654747,226960836,281128475,638327761,826402977,960120671,248684381,696245054,475125771,94463584,105152468,963293177,825635878,936197599,122188792,924923255,759283234,304710512,844758620,622729142,656268375,727549428,711832212,341271436,429670245,217385107,584979859,486557941,454610104,12005309,773418578,683209371,23487847,216406460,192710146,120015677,588591644,401243264,834586423,888090528,392214946,916492016,753018194,787587458,411691682,495464477,772362936,283073018,590486217,449100697,757807724,894112986,873964276,376330103,357405336,14821192,123891964,981859770,603558714,884300,400648613,406669628,407375884,332412969,622640978,69755963,499948572,108427317,343572630,42214749,302294814,536905696,709320331,628829308,303924690,46516667,100028828,691969168,188321651,878299587,873588316,139394045,510198183,244913666,929492082,65701123,434473179,905670800,799512151,701676394,882880177,319069572,517130795,812571894,934531368,326792538,404991770,822109564,91460161,487060496,904311203,842274325,130703424,688974879,66792708,544167874,59419642,883175038,715709264,962296612,798622033,919194656,104741021,497473484,836777662,894828248,59395867,50948673,390452478,932595124,754542611,90720528,358242675,307723156,993851566,726253141,566056792,551704768,652111902,557847796,589509173,196219052,900069369,366367572,357875292,29367892,240747465,434847045,308590124,149326931,822074753,658323702,683893442,867343953,211814049,67482024,983660419,982722380,565242225,433869608,324464158,409974646,189062313,181030467,768715316,976716343,848695193,87984277,56554231,551995065,592838358,178736884,79436524,691126690,773197042,273247729,549489167,503850638,310555243,498410235,842752699,345150625,897596365,558502959,322006192,87970872,812591521,352887042,647579761,422209323,969835799,924129799,112396804,844042162,696370832,954505606,770038900,190432606,912626587,332407302,76347217,281479791,548963126,51568476,442668021,510430071,85502896,903099382,129822516,869379984,374330723,871659354,268594406,322233589,929020970,924010847,660806387,610746423,817867763,703309700,251022778,115887412,708541463,933028156,735489671,724295777,7234328,692848854,513515155,582737816,612704688,94282757,903528687,589211814,917492973,535866466,711643036,476953586,710859076,728352230,518456309,951990052,564609561,424311900,69422667,968509100,241427177,90786035,118290392,787637791,57130588,660599246,493757385,325158077,294740227,66448199,206579938,128509275,641828562,272658930,475586250,737925141,570569111,713758250,877994506,657918516,979151488,828110383,565494937,911161868,734339158,580684414,917935315,485699921,523212015,478167724,64073954,989311058,37680418,108490913,179123434,878541054,376036970,297944592,870848827,654684195,676181994,966611534,430635932,660687801,266065980,895890524,794579605,683195873,989707517,585727560,158413181,577695284,733773776,813697728,338203632,528560819,931093135,48853152,217711641,736613712,521008740,182062699,63124730,25373120,286648524,95914098,158340363,209659997,773913133,350528209,350127186,654039223,286861032,68583787,383648732,82686352,595153859,155989669,494950949,822061623,319706810,472102252,610533910,96283263,378726951,631761624,877460383,102184837,796824107,751320940,951187127,715687767,31789843,56786124,11743451,270218963,832113513,264792638,772073901,948542415,385956802,488197357,115242207,773527150,719689934,461043167,592079623,135376054,591870998,443238957,798104991,635231147,277331395,732499423,332006382,337151924,356868882,560974881,923128435,370867591,818105984,539533680,129278575,475965797,24299042,16230425,50224665,706156951,547945817,103983373,722659129,34460284,636699925,615219644,51108840,549335774,753349450,74313445,845304588,949539568,776122041,825669417,868480980,631121074,844648491,305808923,875504391,145958064,366526430,775083653,73826280,262594048,534832149,410193486,929003833,69652898,560169263,41223240,61502723,512206893,406884464,515582824,590378000,986527381,337550332,802442281,291746398,7299905,143890155,36028416,711784674,929406379,948972130,373933436,754348197,283774716,863019418,418504066,60101063,567156212,680122270,738622062,789333096,519849353,308702693,300682226,827307079,519059148,165102169,120526171,398845697,769881212,749095120,293638541,665874738,606017708,87488127,970549085,644795120,743811481,142234005,932651197,308005774,612480735,364461743,968042901,744292237,139370266,788754843,463556023,924626835,968754093,181286022,48771089,626852909,427590797,163964246,753448373,165958481,83484429,159521337,956437418,606944493,791009342,103887879,194831758,77353717,84296052,222512376,624747461,772897627,872924681,119587605,381671516,775529861,139050508,204674987,162869305,747682364,759958748,252462114,172259120,96035054,544302150,248292724,263747339,41654709,713476140,568972955,454960454,719362601,486041220,541581042,310886895,558032721,761753613,228838063,632157258,417737377,59698564,969007779,890721321,405528618,908603180,690138777,479407350,715231323,821384968,497237893,77569674,744849023,176350023,811779538,853873883,134279008,79174546,826364945,91001805,626767286,814904375,947186879,144717414,110760852,394742264,717483746,658310304,34543495,225266791,750184995,903690437,875774192,704175843,668376998,416891215,927152498,289866872,851262077,569614128,260794851,749199445,222373190,555580846,844437610,121723675,538058336,632508778,471616475,308478608,792158949,800794356,298932324,246500284,293464114,149152053,723640561,847150251,755106641,332529921,415630960,743503661,974219686,430035335,314377864,711926316,607630132,553066267,781420051,818212424,503350856,537064585,778217971,664342489,517883498,353718984,634063949,299272600,788489653,937181869,135977521,896574347,686236903,378755885,356153879,134837137,540843389,315306965,262816032,693741736,110469455,993821125,513442392,374306100,321076375,557671261,351069533,372567969,150860838,835337611,949217243,106884276,963667606,673733291,796173633,163805655,366592200,60038926,193122828,490697522,621278805,496616438,414868184,43206950,442372484,499620373,187156705,14304478,63509224,509431982,879144745,109693692,661469421,949895744,956122219,986868889,524311388,612709231,604489983,978452419,852205859,537048192,316764984,400974774,251787445,668929494,384869221,428110351,634806581,584626712,217473045,206436471,497239955,55786008,98792393,201262697,359400004,450252306,973407938,958515582,536334812,516609526,103260724,537240520,183954807,918010555,356218059,692971452,401336265,384585067,990215251,962369056,574904386,380156217,466091036,757366807,108001693,469306253,879048559,974115488,156549840,939786230,293014722,800869911,303001132,669733437,119116162,231077642,698615648,777123001,654191878,580784316,591519994,745714281,16309326,805200628,305658174,757755365,755998946,257292665,778668327,445740523,402905502,372437634,306924822,42723075,108044546,443214219,270862049,867199120,578877494,418647088,129804314,511247952,714983325,916632798,671722606,835420672,447164309,63009676,493192774,647118274,227352244,260292537,834700563,240404022,426378527,417543403,29525350,452738657,514863897,733559196,433882810,729196970,290683004,702946229,941548940,752353444,760542877,791070334,952245225,505050004,92570123,144026354,923922199,914273906,414509304,277273742,499734209,285829963,115852169,644138746,349221104,84867784,189883827,191541259,96287907,906272764,206241796,57268267,903213965,449195333,50938087,460238675,446255053,178746817,499000273,60623652,156713527,241711403,587768147,396870696,166598457,519672110,189002238,995910934,337443738,626181883,947589978,774275205,719030482,116616898,203012573,775688403,145946122,732956371,752837848,45719385,596806729,106938735,515412542,122943858,414760419,700876635,739344771,613549585,836063950,988940728,941239904,824201678,498489784,574685336,363442517,613401297,259338896,27596048,678976911,160197086,762553637,662639339,709320992,57682321,768987300,605843188,915015772,583705753,520232097,207942754,178998627,707786332,46422067,109048829,907040080,660984271,691001606,653371296,196200115,874246006,887547380,969514792,160561021,816219248,379411640,313287110,424333480,291986808,977480119,524420014,836885764,126595203,305853339,540447552,590682616,280546502,905482275,211651128,625883449,902451330,727981167,118240285,391645158,520619615,627542811,149998032,708639589,611284094,560098082,256785373,732707804,233654598,389961731,427554204,357458370,127703177,566366183,731987937,716635575,807628264,876991738,277467891,689481190,208915851,838961019,811774838,786740794,511216716,169495069,68641248,331202865,67784546,571052611,581877964,661632153,461456036,163229940,535632340,531572242,433432501,937621960,899615638,219392801,105862505,860177021,182873336,884738076,158506174,9781781,802423324,260915575,886195547,408214985,821790233,367945360,169426312,766778275,597825775,206219123,68304254,366198109,593238526,878946273,457559125,445087507,712864369,685177505,63846558,440654701,446782076,16657654,273245458,864875225,662277726,700110268,624272916,806893179,152721682,283222041,580807910,71680636,347204568,83759818,483356072,444608967,505049716,966433712,728102854,532063559,947322488,361975480,436321224,503016720,44088361,400017454,880162742,403542490,682396047,165463472,451107505,402807727,312507124,577260730,226601615,28554744,781851449,566072085,970974547,560527459,70208721,326077020,612594584,167519946,955873727,929617378,325281751,56002102,472102638,715722321,250336591,998750470,284692404,251214422,191234942,262413402,953217376,218614107,36678006,623362708,379866248,360502278,101554108,872323771,966164704,343610970,683759859,132613505,153308517,572642905,56689,793741812,463723579,821960234,706446250,418140014,432375856,586634505,906092422,729551992,23985475,273221333,185556295,716155458,386561027,441284309,521568419,294636621,695057325,81533625,585623086,202492098,272297090,382667129,735618887,836517455,55563211,112251804,370355396,621964552,21751550,642694973,40901782,181500971,399157972,813730353,596814710,673661569,810767616,912081463,739485516,701975302,998603954,880557988,414750141,942356598,975197746,598675405,685060604,408846811,267436924,136565516,279562840,419600925,8447059,575836854,405872217,672628588,376614499,855935730,854726246,982591411,194975616,725177341,541631486,147725601,680135992,863148649,113291434,837208456,848803886,580908300,835778355,138281650,510222311,969368554,501779406,632773436,44239836,462085639,247700666,827169746,187721127,890256695,449738615,942982696,671822017,533941335,62535252,730522558,522701104,395043499,150392707,789050141,101261356,633660981,218331202,334474865,94674257,105162180,457573187,269088839,745404889,675568652,899921620,390564116,26019631,389008925,247808119,927711125,946982662,450315240,418080362,766972199,978707347,779798413,501103879,698245671,227010645,333417953,281148230,239078865,225725405,231499489,456048249,953079729,921974785,515039131,207492352,23035763,307104392,691664452,460884238,734646575,615417354,120564280,260832277,202908779,40529714,350204824,596325896,180233062,431769355,770291173,891921367,678195595,812850258,705641696,236434465,623745118,407720403,785451841,355284859,753555197,542129116,767651018,168600915,822723407,79290499,112202618,809388544,117727525,20931387,441034276,866722159,622920219,962771154,969528956,849984104,720272560,704633516,395113419,372401567,662436489,198625505,858563152,796275501,880308446,379546114,443035192,399315855,968417893,424947572,489019328,888781677,230494186,636716228,338852165,970291168,751461609,432207724,643733761,317988962,540082784,980564571,870795643,588585855,164429245,272747946,355348758,873850347,815028703,870872922,953469551,630620027,370935628,47589116,994872611,844373232,949133966,126142735,394056249,613028689,189680449,671364051,714728194,976026096,61098916,715997704,888412449,76494476,155485714,678300425,406668095,535312234,802993500,33901952,945840382,122316953,401481778,771353419,430646454,694720337,754568227,862230823,777487614,942534125,799658450,899750263,305236707,85427500,25333598,327040797,749390374,165483699,742436861,617970755,756120646,524188284,764521945,876714229,852619062,698114841,156413018,493834661,672594880,282368149,635313537,57286512,514622634,975869088,161213723,482785945,881333953,623211384,250796184,673899378,119332646,995195500,261928619,2184942,107867532,990318290,297605650,882630804,606809595,552182541,764697695,277798958,72130627,13354070,312997644,981387457,642613764,179421247,293480712,285638862,518167897,86763102,529378428,212730464,695104836,239019628,388379267,360616759,306980887,209736596,299948108,363417690,247616427,453496801,644624485,443765799,246203952,532531979,433627353,772956579,45315336,629708046,302487444,901887655,307109166,408285513,844855573,438663527,995121574,57660422,372688782,664474588,207869738,82479868,552108943,335968000,302476100,915551715,313731863,484394711,99716123,284331562,279296975,771396137,42698390,450135025,769725408,171976092,48728880,495074835,414649088,689569744,42251930,576558748,202816873,290987103,786964668,532472044,751379003,72938233,789813957,755329304,443615966,722517135,650898927,658823665,69024403,465737846,957886260,424337721,19694733,516882821,135455579,179548582,697709836,60454575,798413164,524701788,699491766,723390752,578909316,882523129,284326010,144251450,868456028,228925260,839553941,202765756,338693758,407930801,486641471,720279229,614679906,889691998,746368460,463352868,162533951,760545623,392487044,40909469,887754988,146590303,792979836,977567711,790446558,503481658,809651725,230012689,57262745,400112345,646512188,127151750,973039144,657304065,121546882,924077076,743075846,154717020,633450864,391238850,820883810,254835273,291773923,564452973,452472363,257809830,302594217,869351076,53505766,746940715,822804987,844663318,110648743,190172288,735190566,557971706,950223518,553604088,75111084,841843471,785946111,240188911,814289773,819498468,634900030,226439598,430636040,357641341,135648849,388634977,826044768,587917033,713322448,972513353,998810424,216659218,363940698,658369809,538053845,697280606,528664547,122096825,631058006,804983996,277188217,187067911,523770044,665690929,792597689,841439648,776415743,992444801,149371921,624482218,611707060,88237221,749216423,148372995,77132852,884728854,115404998,971674982,935650283,62457467,62977378,94769917,791509615,310199159,958414041,81947154,386666706,253034509,760743795,94931883,258313702,318487669,666414530,401057618,767353921,499609558,558297054,830478891,192208462,134357656,211704011,107430525,239997148,660354928,851168188,622953409,831628176,633222452,961062608,421588911,478516335,723216386,23263219,1273300,823485618,586634287,35156019,215842981,140494233,573338914,445987007,332360375,586498428,815776528,313830423,475108436,100329914,566209636,733396115,159846645,576473858,778042001,261642122,735559170,419797047,461292194,224296777,912135490,971056707,426899448,628683034,698621169,104294286,354833723,440904158,727163504,783464344,89876892,68757775,9182328,842198528,570325655,400876315,403057198,747864775,490235014,726557919,839905070,213073622,516490534,967983293,979918261,667841473,32755269,137983601,321600078,117664148,428133346,451001390,72639532,888752900,275133028,105600329,640802858,731301056,830613661,814623415,689309931,137571115,828465668,956296373,471424621,132472431,168777709,322095351,4285106,476400029,685377891,716863175,23334200,548541253,401876271,647066714,361516176,449103278,666847750,481938597,454316761,842059260,288725240,534791084,838128288,366654751,377312138,638553341,437396536,209697904,924240195,115582652,665685165,460373520,730828886,406045914,611270439,985634758,211065000,867198216,148240246,693812354,664339285,166951848,493066884,820582346,397689681,753087511,862648201,55878711,568897475,422488488,856497012,80909215,933105014,289381259,207775925,995590667,613217482,25383947,634207326,92534495,463694576,644275074,329231750,333641671,623478066,329939918,543553733,86410638,238192330,525820263,201226563,969740258,48457082,365287413,311656419,677960655,534261620,503505594,232365032,283753969,501298235,372220306,755564020,730333623,142854332,477722377,795470344,178088403,423538564,535330510,826746898,49374522,573607956,592731323,542288281,947684588,765006736,448757849,21528663,998313440,44670526,315055011,18580820,107086040,896513809,978993768,359228084,7892978,63627570,630414822,404786032,472972317,968712152,204890289,759566693,370922325,361434011,494271364,975018872,826385016,827675939,65068095,645192091,211984197,397906489,58091378,845541439,269697345,508465514,303412107,962731170,817056808,383961685,331796145,228763389,525536467,428086464,624153827,276066584,864087143,40454405,957086319,531559074,639854466,322365588,852615653,990084408,528529946,918806604,125269754,552475739,566775843,885443696,72851865,254890706,362191186,858439698,30858824,591830198,619050964,857592731,166220465,32563269,636145966,557518460,223237764,467497455,356195983,348857508,832934526,915609362,90123808,870929283,304180579,9573928,519668530,34464073,639765281,674816256,670657487,788872480,161956233,360022629,217792749,256045446,43499426,657223366,725086355,636907567,544650129,161597596,717243256,611528406,967946242,95113717,490683600,274182232,834194079,388012469,877586563,247313164,516999786,328343482,291675818,780440954,778059636,943606817,76542157,825086048,512615645,30439278,792021257,467170501,879030738,499990337,613361997,577024866,112549299,699970609,468066841,531441376,574055597,818125145,392543422,385977296,178745826,76663856,202594918,52277739,469368776,226250994,720178015,311260628,723070732,737187017,864773760,607992547,218227468,834920475,885957226,442006028,835635191,238453,542840127,821275672,696746554,396803465,375642782,425332468,691649770,776410140,701524405,674670830,16675933,425235946,126368341,327605173,639791079,719513698,484209646,688275182,543482880,866763899,636325582,591866432,281496422,160590205,564559351,41722930,902753668,755362189,454270154,47754334,788015955,825968629,7382721,584402727,891118613,476351100,138338120,140078639,77016336,840333435,452863482,269265154,250025578,77006726,551216163,288220778,877996775,930615796,131794898,282257217,376757936,812247456,893780580,109715894,738733245,285334317,647646818,125519628,103315149,488242013,539043253,839601084,50723253,752948580,742177930,423197554,518920530,899730767,437667943,315504275,640618506,463886763,33884882,175539546,458762159,835217615,618342570,720035930,808117028,701119493,755577187,382100335,669659397,85781977,4042219,431022080,744630889,630043565,12458631,400434263,735583520,203318637,290866964,396496871,31183763,920604699,81465698,452400472,895304171,552942057,191198120,474820309,973336996,82247988,82250488,457304262,634363343,289724820,500460136,504921164,302478059,366678392,786462215,93898083,963234698,484349548,651905786,734025025,493026756,385569618,656343689,677758404,764860965,175426699,388583487,636637593,578773846,672336198,251140146,877099042,210446229,268714352,518789225,364295862,787375409,681433427,837680504,672502483,576487526,625833778,872276232,280481312,511073365,344229820,508172356,757222098,359243214,14389028,414432759,347435633,418153810,657312937,614452268,424833017,117852363,105622966,765544337,301139982,728701650,270983604,279245649,389234173,922045289,856393499,634189935,679278907,833102419,409539098,624455900,809509844,202713463,410937190,587131416,226079854,293047864,22251803,706359185,120775595,207077163,524299074,540128132,285991144,16354473,786687301,202203528,475614074,12464292,671178504,799009204,769064011,536399311,372927276,397015275,904907528,576212578,480537710,949040772,909175348,710317169,929852363,342629311,307617391,706994050,101993851,24811454,519196955,118078527,848827696,292398434,591497200,280953111,74489468,914906030,23869103,811552360,197434876,849617556,949541021,970284660,139923270,643731069,437120168,770472930,278046132,273833553,37413310,70725076,870650829,161973090,581948886,868663919,546313438,817048398,155265562,447968536,956120881,761129578,311332871,891738337,922156327,316564043,767614528,447051441,742115898,40490165,331084842,664355176,623718624,351101854,419340415,858476550,48501443,780345258,912716504,807963487,879160054,553138070,309067784,831124929,591830505,406305980,135859379,597825707,333570317,751568535,653743002,669441965,144604347,978077626,18656488,843287740,451846402,737657722,906957623,966977283,911405697,531756873,929849737,747631464,159833544,993682228,410833023,100334691,96228373,996952984,209656849,468373333,172077854,144892877,868504717,402879647,939019693,117084256,687722066,638176018,778442715,740382153,466344630,222377753,576454187,166663103,251898132,64678252,6282945,785788227,968724449,441894211,721579476,785790815,156849748,993674640,175209732,207255316,85485423,316139104,4383416,388992388,705812672,76227974,447490087,192480789,880099832,833542358,790620266,814000702,803403353,356410183,627212707,242565324,152663087,65577644,570270687,146045801,193870098,443840380,936758641,384577302,759222367,902665094,258864731,357176793,328635833,867289578,28531362,431264305,683125228,648536892,519339772,369742809,222422147,689289779,549664545,846981614,111761754,981573815,290944638,123753348,955544126,954995980,655898129,967068,712385511,930038232,701063140,956066133,345018197,685631370,644745913,766067872,839862772,970758885,299178860,547709834,814955321,469390475,208791358,473660229,698440907,265167672,249045158,123155530,916558498,766392213,142895468,904874242,364697062,784710758,521981607,123373740,953788346,383194325,88430554,791983627,910435861,730928739,193299529,778171177,735666273,864806383,489626837,955695511,491232849,646305305,139401691,533333365,161424223,815718459,69084719,825273997,625709327,108379948,109589497,88309235,668577406,409870981,620004701,101056259,256313049,467118806,712937751,872184826,17687479,400654167,691061165,197473874,165736867,328302200,762133759,387234344,271971598,834110789,80240529,694147121,489518872,933518427,150512370,676441615,944671267,204988204,533487569,613809769,203610779,932501226,227139004,903225160,517265250,729524661,983443437,944686961,116881435,99832684,253518272,838720911,58086147,32796194,381537180,62438687,350094297,499832495,676747561,826650535,500761471,154578697,260419416,649643867,901451406,362974508,85110609,741622125,302404072,459752541,448346563,351831781,92192557,674682651,72068437,681261090,489221701,83792286,628358622,790621225,446843818,404946958,287543001,926938050,123341407,546278509,674586753,236220964,97050569,657692650,598418385,179006050,392780977,462407469,767305636,679871598,263279649,995901554,779243552,822702441,660769146,630823746,227569895,989609342,800931952,691114306,405348831,330851708,568710091,354446956,559432307,995667078,456630660,921080473,304275132,305817046,142210689,695869643,882157206,294284499,800557081,293644648,26627377,405486879,293374240,357878837,934392895,190777271,333426079,910604335,304035647,392788938,356114114,554310884,747198987,832091764,345739482,179423661,135083499,207178994,67047591,174079747,255297258,638195831,599949879,440689363,366436740,567228385,435862329,284332588,911948202,824753197,851353980,407543640,988208957,926767901,677622035,247048801,304937373,246849618,94846416,610455900,572795674,783922645,378402738,597878894,277771189,863862655,510685261,654348952,937542839,479719436,264822432,93430598,193815951,88589217,154270380,652573872,712482487,349451286,344256964,427849488,96374241,534333592,138500216,511392821,325066817,147104568,265144738,272088635,972042253,944389707,233180887,999435631,808881768,17259888,153941047,245092646,976557434,675354795,894859611,61742729,355018034,90229417,989650791,572848705,223675824,120057108,102453665,744596779,210751609,941125676,319065440,544614875,336018719,875474464,411722852,782854214,250925950,462013286,809937177,505359497,534852781,712276349,430521287,218691415,509252285,58625404,815722458,551864533,951018993,112151649,658818614,672855571,207811182,303071033,307208625,28745938,230221890,915049830,309047338,596154594,336720271,24857784,673204627,295000401,228639823,556113123,419452116,430251953,735099724,150720706,724109031,272035022,485238760,847100802,164159791,379988140,733253917,925057011,732538213,865327274,531202033,192181460,413115525,527389393,712158227,312739583,499320621,490790326,874498579,997127056,712565471,237332263,106703653,656727648,816437722,982125666,214407277,538259801,948232531,905426768,103674753,546317302,187597193,445747872,521103489,736460451,363984209,460405359,539782061,18258999,462564253,717169070,3424173,204878869,176938308,732338628,280291490,42944007,120006636,790624854,807108242,728769297,912254315,377621418,735876148,426269143,394301053,619279635,260486917,772762742,198741330,123924456,249430550,244529074,666916338,100665148,30844833,903070522,322228642,322544298,638036504,671623504,748246488,737302411,655638995,224676517,686888419,30872456,496636547,97230558,917500461,640018594,519544119,688758371,471996451,343618523,959567825,330338125,68601172,648925124,331824835,94386357,682868631,790042423,711825871,477444533,849529853,796222951,67948081,158102792,372323955,923497600,884179835,175776073,426674711,559587659,995714486,353838731,482338103,719906414,392963598,602406769,294543676,493681054,806578673,569838873,893482865,34170837,124172752,127541494,304664625,343054288,6484918,118937078,926356041,408765492,889394024,304268328,108639151,183315325,827745954,531251546,484909276,634512236,121169963,984902132,433936926,430147787,483343062,74481170,438459904,739308592,381029930,207954857,975006381,474290180,152988833,539994085,37546474,628809068,536625722,622059455,995989158,48629220,633667990,858582124,737468398,87910559,398965600,43223365,208131010,403975775,874826478,734219246,988698075,669534099,420372771,539062788,439210656,363715600,630079806,620624133,260708104,101389030,645872617,692231965,76978266,129606406,542156756,94353103,28398516,436688236,193111999,106860885,58780107,155861487,175675366,728416600,229236723,574811553,495329456,473122982,928661348,450375196,21658153,213013493,973836977,586644383,47407860,932710633,638715412,252836093,878676082,200384016,429523527,864393508,635282460,415736860,5359765,705262794,709254182,728071545,364846347,978831812,322736796,237903210,747040228,498048215,284802892,942656671,186651764,515756259,735122854,536528284,803102550,361137218,863811333,577877464,894439348,556743110,438234619,862942297,307844212,34025123,569569258,170112521,350265061,727073748,53576151,54695218,444542729,148301372,12255792,858412373,851960425,536992598,516996037,916796789,803660688,201040909,771300770,705143649,685933027,854112695,747466625,638472512,828874929,946903861,947138967,472010062,84015601,200154305,524452177,867322282,328586994,699952152,355032244,372918706,581712234,811109790,836675727,591717157,151814882,961028416,220385463,366520319,469572892,144503431,14293231,685106769,334562624,226386216,767025701,528357563,218011853,59235261,905191703,472355452,356077602,430235774,303550573,796959904,285160855,52982121,198909673,76102937,902505819,563752654,403420497,485345751,807513339,488320848,882861668,360881016,301929254,89216042,217501067,854723421,998826326,567607931,513898215,742439952,946208090,449032361,588213413,173877786,455493147,226987238,367868855,437483892,18763210,52650980,301028063,234283657,62781342,85421285,858488979,828133483,474542138,880599453,804411173,709381684,205400240,525718657,458026298,514547643,289152347,528791801,587418179,947883782,678388161,296240915,740384328,336089310,414314355,851832406,784750489,865696306,823557474,810627420,727641984,308376810,825413790,554621978,694937458,773496105,161163624,490891317,247319775,371266547,61472845,824910824,235641078,541583492,39598796,263597485,820685076,353277177,472849383,346769796,909507738,180404300,643743485,487629838,624508331,566059330,872965008,429172237,471937347,841204809,285308432,838059784,911376492,154307827,239339430,145630457,188499990,184565174,304117153,491366545,485652472,234523135,988660988,33903333,946947232,669885265,911316019,170678515,594145430,654849274,637751584,363439510,33340510,600031337,111777978,215553855,692964472,540335946,140939369,340509968,867405428,434445899,333688650,965826521,857141127,883449280,322008942,466363801,481253545,282283658,353615378,635061763,533728678,505948181,611056039,199300452,282899638,495873628,855834851,574613630,71040873,23439479,477847234,839319835,667216923,805605327,750036101,428278173,401535809,564440011,176635411,419076329,794038383,979347894,137153838,274737658,65980605,833677654,773277744,584485088,966792994,130487025,912381374,585173250,645302383,789777778,369906846,750110945,321317692,517778786,179042064,780264671,808034260,866836623,320446925,337171342,48035672,499954881,898305843,877460322,566073608,26221340,686741504,383674490,817381742,118369343,54494372,515482443,217344668,181351649,653064793,945674687,229031329,157258869,891887806,105536225,210576986,365491162,433015232,185522201,292786989,866541333,394579149,749725818,434976058,813920649,657106513,965058899,292124689,467158903,587066832,888707284,484842295,305910326,317243753,313507405,593623271,637921380,822953048,612749858,831178297,147747187,177247598,22365258,46895538,853906639,737302576,210689808,812873845,290227303,538857831,112957883,902295214,253567768,905479962,810739629,459657257,920884713,181349434,139239835,99801056,39714859,909702972,894067570,58781334,624237705,170228523,794007736,777807729,245011823,369274856,877529208,967487856,669406624,770417272,28901134,385612794,438680143,571944237,825080245,176247748,812852665,180093173,988052758,411800356,469306576,321146713,81664652,21668341,347625840,323601827,37073074,827572808,804195136,209780934,310014088,901598659,10738284,726954273,207118490,128916870,606210322,6358181,528718846,622617168,537680858,416440891,277600299,855316985,116698825,515359439,472986329,492315209,909508781,131738329,254649997,960192210,858817839,381288648,718388325,357640492,106138030,197125010,37500855,363785160,70024423,459843422,607205688,982512303,666651089,239881492,295795111,544082903,71477044,93823152,781596451,215222747,504366165,235608004,960787636,370247269,177513474,399087010,265641792,103388241,237911724,236267171,209251526,877640802,315473069,761176605,298799562,954209493,698399921,649276241,524119535,671558105,353088561,668290533,370749274,385461176,222679275,620709111,659307401,578361390,779735279,178463715,129873183,577703583,578361827,555237500,661714717,436516684,610404789,944291566,135931267,322692508,906645683,699978040,323010976,644767085,282027035,830144847,271039482,952526966,277153041,938847198,638341643,156733423,982717809,67990450,599977577,770511968,878044581,776679268,221794585,653000116,657890757,228746779,456898608,339675812,347634083,287870835,651183072,598099375,42996227,369164818,778355430,960061578,190911922,963532470,577993775,287137547,835258687,316950234,292521666,162457752,138803149,501008350,838251712,937749643,938093313,926811555,98015692,95574925,456586556,63393436,795854496,922979947,856306352,744185092,534997780,531629763,827099199,239406654,45091503,615335259,448626742,879358913,18174904,923049179,350547460,646264819,777740988,910528803,798274142,937540881,810887764,705804819,600372513,383768488,890610628,882360975,76944272,780353953,294007623,416167237,955178552,788059679,162444558,485255421,643315525,230683345,928939569,400277192,793095409,928201973,88578461,34453879,429276548,11828743,886083788,788064206,545879589,275362191,576114055,590640544,818088729,210910592,518746763,122794317,481111468,6793557,325781398,76212430,619245145,865801426,683786067,695116151,668250394,669307979,783008100,731766629,913814718,185627223,733389337,73215246,386659106,933450547,249691102,27347611,361240099,856756209,19721038,390362327,625788217,213142876,186442281,397068911,553080741,578704032,508104597,991489971,435409029,957154944,999020529,394805243,947865367,487020505,495850934,61599312,126630832,661771033,671950082,257738242,474273129,192038832,895582377,933546818,996827758,5375621,442945764,703967233,899769873,635886303,916717023,561981362,108122369,705795286,627739753,539016481,726072827,415877044,935372677,570202043,631317837,292498930,422093534,170332447,284405050,969868484,615478199,357990831,117374315,490078155,173451695,875905939,822711159,297878454,82685947,385165796,577981388,904359457,466363290,82820082,321573592,233956015,590046000,610677133,488227566,829904410,223008126,789274565,432377229,418374404,372678324,906124557,772204919,294760089,652048295,568460866,291091130,266440510,275374488,308877616,968078884,324835568,383149155,167700845,453951416,372190671,981069230,460942047,585509467,447561522,944495924,979828501,836393276,199538647,456368992,582394668,260640124,679781963,696068326,788782469,693503370,358827178,587920341,57173261,394419603,252483137,264199721,176433625,122993294,177266667,861276754,834210472,441563783,336714092,261044879,528709728,501080549,811802438,188395518,622042696,324635288,380143185,204120943,855275027,69899055,239152010,529973101,762512107,315489995,464962083,441579208,169189316,629967560,557862202,239367737,317630523,195632998,463297827,344905935,725251062,954488381,631641444,219794741,907782947,760972496,803073793,219145154,855745121,297403654,885762001,419774617,90308728,949662586,963349930,293019851,633235535,658024194,730449748,974095033,934045996,879389938,193431845,397852985,872300410,417122868,597383964,665316030,294611005,66918308,360461310,915901264,508750119,754865254,876918660,814142193,351378726,377335392,949635438,864913220,185018820,51799480,600092086,74117503,363613497,22488903,634873401,165518904,664830529,255133499,461053558,799212370,619748638,780354624,730175011,682141494,212844594,359234808,963457426,419942187,731822999,31482560,164343137,381473811,346455144,89236615,186481613,467940357,984301431,581135041,751910149,605052539,845823397,668528369,949891094,499526622,963582417,126890846,687149037,598808562,791388546,389378658,55066146,127840935,698709985,565937016,345247492,545972479,859607608,964276499,934352314,952155421,370557987,905579139,625048071,629749031,869576842,409703885,630191368,608001817,92599702,117639282,587080451,793693048,280583443,201363771,493530198,709275266,778300885,383725772,770366864,502153357,173054667,787776255,287342497,133830228,834417185,775088518,116057521,200847430,177471932,915927518,505424036,983420462,478911548,263071880,664853359,803268078,286192013,567302077,592346442,119701491,514090401,707143424,353174834,309663513,893448030,313763540,665849815,462192998,739026499,474354432,979188143,793559883,296992646,815852962,357719883,990226497,98545391,881203096,411696579,965830619,521950690,83457994,282516364,205647405,953994636,143973835,267145621,109231039,150200649,150593621,76642337,624550077,613411027,224039795,23233951,357134997,63941998,795831357,202128772,313550829,426971297,326198326,234406370,534003743,107343782,862618368,106110937,818424675,65856749,321582625,990727402,24310941,964062576,962482987,831328983,891670423,59721169,269031920,883604777,101764900,47059881,261748065,850165591,515270597,595389806,985032823,445762837,11664596,669730623,903064870,864234737,239418951,748553050,972819493,445263126,517764284,816970677,805106964,457370278,767069913,441266486,858699746,366534770,652958529,39113575,424780749,910088017,706083209,414660273,460119424,33849559,148768007,701801270,467469680,435237048,826094055,27484604,941075320,525631276,272441308,133900719,872153739,125043550,435673155,302211215,229375471,899708848,191700302,29021827,743381786,819073185,814291398,876014824,990881126,170973642,138574831,427406178,364191432,815365193,149412503,717992127,295586286,977871081,151789205,304498817,844884142,228108547,96327040,609244683,463681041,592695779,629039957,936403480,648028591,163577392,142006291,311653949,546403226,687158100,442140961,978877555,740690451,699382771,41862374,402225751,280927232,838919519,880691711,380953109,909124070,235898176,731617352,341219368,762303285,516977151,834238787,7755894,428189183,176984206,259968841,694049960,600054961,640870470,967567894,558968918,230153768,621748783,459656116,216704754,621692124,483452187,416683419,878347077,798740436,95641311,907070707,72036527,776548650,965513563,355797935,49597982,236217126,834242589,58004158,594301640,177348039,958673263,334566592,885039967,772479921,224858632,41688515,912226954,479265524,999966526,163774244,61003405,553476677,581994149,338316844,88340571,197149574,689622956,494849064,409416421,978481210,560678570,536441669,622766824,382938225,599908811,681528673,511916175,325475216,458030621,117139442,128391782,250266522,773159340,328051318,530959664,415627863,789125385,335084781,520728772,711055206,213670317,542151013,259961648,481354027,942172142,7052637,449287332,393267992,378250814,272515775,982323267,328622283,869754893,225075261,13903146,201903086,668495173,510419281,107002172,452871125,298576020,701900751,595917625,313409127,518507185,936033006,505776051,702692479,373880647,346439321,778880509,154715798,59491091,426814281,603913757,97268244,732647662,52107477,632018883,767842666,989851744,969387631,268488281,202788974,997647549,815431783,205364564,899282035,370242802,561139967,804537040,97625433,696911234,629808619,618763557,426642997,208308610,586653645,220029021,995646263,268407873,802844635,401592983,251530268,345976517,804349496,905243246,505125212,495847163,570821639,890852733,565076933,217916133,325783917,438653023,506590024,362123085,300644413,939288924,382098269,364145465,632339040,158925044,641339781,343838768,197118312,450783366,985020067,109832508,927617348,440948135,136242455,365302204,578733037,598196104,279611082,554829455,695726192,941993248,167807636,316469173,351473445,302808990,396388388,234827031,202193748,498660720,812478139,540443186,527469685,849220462,10608813,579414009,871094666,363631017,50570389,614778871,541366599,149449161,48734545,906649135,250777611,487845353,584640943,635438997,991172691,571250126,715284022,91248916,336339063,680219430,467085668,682345611,193207189,752472647,890435249,87146982,45744078,116416220,45524869,602605224,618635229,788560893,795403569,727183533,968613626,268219733,461387350,263178266,68260786,623609914,224050147,89035802,481540676,832249459,839702001,510182655,9429378,500417745,934222451,553221389,918931571,977124113,46777773,302233315,856704270,976290321,932358351,180781345,385325018,587286360,819779857,700888214,840612465,855035997,97482939,69099001,672835364,793520360,765584926,690527607,898397937,482759491,965885537,380977716,437884435,552180414,868097175,823121309,468239448,101597346,25079892,131747596,658155501,399224313,29039543,481410260,784206937,626384798,631309897,409058183,420815809,782571241,406265310,421981114,720459679,442155023,625613290,256227815,770871894,715474281,31910500,524834124,641894125,457052848,259023039,689002425,875812552,46185495,980610924,822553627,134232449,443909535,390213041,196763277,3011609,403794536,100989796,450767878,410673579,59672349,813036213,882497697,832983693,73173019,276301630,43768965,939219452,827109232,332446093,637061976,35345149,131644598,947082518,816354981,953023053,381739020,464658926,952236601,225922399,836006004,812595978,640061679,52884982,601333946,701127217,663934997,265843881,860695848,706868153,459638783,979128283,493258959,948035670,163504562,352885392,995580774,421089494,90384288,467969507,263907469,929492309,915633558,803518767,216311516,231802011,484768622,765111056,339509702,717455728,15920254,282182286,811239171,190713393,292123800,184813993,394632802,437236461,382369284,66270530,345420080,785797374,547069087,113346525,270937247,82083415,83147086,665596000,274362593,188745797,109815854,865854697,99876685,431916839,371588247,899424667,527192098,247575598,25011733,546205688,294715281,732457450,806441572,928696329,480542856,82525026,593298445,755131855,484271331,493835386,433941810,427815685,108607956,414569152,163065036,945911829,35386897,144598143,601093646,67804826,717404586,966349753,629194640,395221254,359736855,623181988,755604678,506502321,962524737,665857628,491637260,864458225,850110708,139818972,641904122,761618993,989442024,433403638,415174927,257717217,512087873,271634057,186738463,867621041,690280720,961253627,625557400,559845125,693038766,440701834,759671845,913996813,712828093,605150269,399874216,784907576,271643263,922248939,504610812,664321204,301826305,159206055,650362765,247755454,551689956};
int T;
char s[100010];
int len;

LL c[8020];
int n;

inline LL Pow(LL a, LL b, LL Mod){ LL ret(1); for (; b; b >>= 1, (a *= a) %= Mod) if (b & 1) (ret *= a) %= Mod; return ret;}    


LL calc(int x){
    if (x == 0LL) return 1LL;
    int k = x / 166666;

    LL ret = fac[k] % mod;
    for (LL i = c[k] + 1; i <= x; ++i) (ret *= i) %= mod;
    return ret;
}

int main(){

    rep(i, 1, 6020) c[i] = (LL)i * 166666LL;

    scanf("%d", &T);
    while (T--){
        scanf("%d%s", &n, s);
        len = strlen(s);
        if (n & 1){
            puts("0");
            continue;
        }

        if (n < len){
            puts("0");
            continue;
        }

        if (len & 1){
            puts("0");
            continue;
        }


        int k = (n - len) / 2;
        int s = k, t = 2 * k + 1;
        int w = t - s;
        LL a1 = 0, a2 = 0, a3 = 0;

        a1 = calc(t);
        a2 = calc(s);
        a3 = calc(w);

        LL ans = a1;
        (ans *= Pow(a2, mod - 2, mod)) %= mod;
        (ans *= Pow(a3, mod - 2, mod)) %= mod;
        printf("%I64d\n", ans % mod);
    }

    return 0;


}