#include<iostream>
using namespace std;
const int MOD=1000000007;
long long ans[10000] = {0,0
,0,0,1,9,216,7570,357435,22040361,721632017,261965794
,238743352,31898861,586572231,154401239,107514188,777072954,996948267,214876248,603786866,505607723
,743248422,997403167,963757777,140776989,131882365,100337001,917072546,526614025,293058611,7580455
,181650345,892807287,521455831,919449940,86085608,351752092,923595854,888607281,785545733,736297805
,322945805,397872842,80082349,761992613,754355071,47035016,713504250,571106674,257502885,889396395
,599492348,415407641,667233338,520969300,713065999,156829682,815754433,11588094,871897082,428023074
,826007983,284403777,148351585,632670539,717645087,924307305,792180447,871801410,465835616,915837304
,221147546,475205640,906817470,902085923,120313408,370619570,854729614,689694360,848148323,670868698
,831957227,960005160,933154024,758717449,594842321,822270332,715549814,156808280,863326788,911833437
,427441474,304798817,605484495,512152406,838540719,10694238,997200859,289945915,39634622,399174814
,301586104,551901947,315004903,202157551,823146534,220496641,244892445,83468605,283695355,154255058
,92812962,172601897,342653028,859365896,932794098,878876110,140276668,129184634,66671486,849830805
,724127364,485114412,246627015,723900065,57312531,115412348,202654809,761870534,437456941,489914162
,946084046,890519461,461944415,708993166,255520856,176908420,21593780,808840414,434864701,782773463
,786586000,18390699,811486564,611501714,685583546,176517868,721012158,258237175,188211238,659113078
,284929670,383671161,92610193,815588648,450871251,345853205,193883267,258635480,293107566,309960674
,356281741,722970587,688620165,727821514,924449797,323762637,730512597,843680001,59153166,166780248
,835197516,649539327,297519232,239178515,626059639,354897653,555217847,983482090,762235847,853286628
,822211909,461478221,823442374,52162738,664642982,999286882,864818196,249014684,330013794,146465926
,127864530,147563546,278663801,793615331,375360917,377699002,669622276,954317876,328885164,355963750
,771253501,492129250,486490111,302746256,634788796,13737041,838864591,754878964,262783816,847280635
,234069738,375764223,160508096,857352000,256048688,948338964,337689028,639380766,239237256,867075975
,579196431,412875990,958869298,112069005,828719439,761211575,999120826,257725278,919938355,529639935
,249519305,517554082,77554410,889456556,219864377,208629680,101836137,74171429,151737206,952805910
,980556942,250800964,565047894,491692019,300747534,897151792,781847110,869901190,565379492,125388592
,602157893,908676222,73814419,336882352,584241116,349506247,123366852,25833623,633205670,881145441
,487850256,432236404,949604169,7873504,681919677,24257916,640535434,177712938,917639900,660188404
,867113798,708708951,506666664,837274209,73656936,154209473,354011149,890352773,693172906,724631184
,502244214,828671385,530585217,875103390,913689287,257319976,28773783,780290854,309130040,366666896
,474378280,453215113,967137819,128445781,984957604,983248953,688220467,202121598,806244205,613544921
,249714782,29415919,754228156,543200507,672338501,584187559,652238858,376056357,231234518,691987451
,46920630,310223919,143418740,832090268,212343588,615732235,978106540,888547246,734902400,177682241
,560257275,905729639,51225820,449004847,383013982,172114205,499813127,495596058,617189895,340507895
,739913413,766474752,175130535,157879531,494003717,519156631,644270945,767345335,642980494,817071557
,993537021,668912470,290336435,319741367,638172011,627395867,991153035,437002755,979776045,384543838
,233681074,29104704,312627800,309008386,704109430,739906651,661774573,227799691,103090044,777719098
,272526649,240592947,142191332,968717718,36923128,311325354,951229484,130191195,300157927,955502811
,617746390,341865031,990822625,503357538,470532865,336126323,272939266,139557648,771595952,85914248
,242066074,309592682,759534136,284296085,92317866,431321370,215776540,298983534,786594309,407542125
,152695700,459102718,100953620,775547332,613078602,488392101,613394673,812501815,733742939,157476579
,547799105,386757371,277947693,448327632,169079401,107021291,503360019,903429018,252129940,476433535
,55560379,718266743,337744935,782642649,88158084,411611038,987873381,8025211,212532815,358844288
,691339267,399577595,846612195,360520639,473937904,932164377,375172359,331458211,761650490,893907932
,492265554,997784014,369060103,766222811,117279465,921428450,123120715,953889698,985216301,274142750
,61990237,331864814,852463263,809037032,654373420,518928379,498239307,675363389,260159034,743446319
,199659123,419544655,894099643,901437540,51721889,544399611,129395019,379334424,730418904,397889775
,268650276,596771014,128040745,863064675,498718889,979821784,705457381,467248628,867132598,65671479
,751211474,761875136,530230083,968537119,250462417,501749534,671453553,842031327,413776795,905744032
,375015540,227799012,144403015,524019622,182300099,242170848,932679473,103446682,857662086,477709678
,579062693,531281744,965436332,869452197,682962397,677854506,251607860,80369040,766779863,844011152
};

int main(){
    freopen("grafy.in","r",stdin);
    freopen("grafy.out","w",stdout);
    int n;
    cin>>n;
    cout<<ans[n+1]<<endl;
    return 0;
}