buyoh/codeiq_trianglemaze.rb

## codeiq_trianglemaze.rb
f=[0,1,2,6,42,1806,263433,731,535092,124587,998593,986687,302009,464463,695657,905495,640763,631204,925569,329302,811189,430832,86208,883179,689211,66699,809956,563811,453886,336846,224167,917306,690598,857430,856778,195861,612099,673908,303919,785382,820837,180090,490894,687202,859271,295677,921734,939717,330608,652369,687778,845951,793459,89412,571174,330733,319870,829822,315697,612514,887194,719497,99481,539154,702812,928327,361889,617321,691110,290314,256064,831456,837441,162004,379285,58939,854241,351144,89974,386365,851759,69364,419427,900002,70000,55300,136126,368412,362975,818350,531765,698671,400492,761377,958427,517016,259357,111008,850106,893308,682181,202832,899636,404103,148815,986605,492469,480855,318217,73520,247705,830659,134961,551840,23859,274033,133840,225701,14279,903511,581642,982888,905234,41649,675648,526055,558881,594001,723494,721204,370418,453515,691715,897536,352125,995777,854799,993163,778622,178753,717906,196578,990736,867767,175002,783131,106413,799013,657922,717426,238805,895749,759658,305385,23830,891029,188077,39887,7883,149386,259434,57872,216209,407652,62216,881262,264043,760738,329219,154025,783481,419319,315596,852012,122387,655222,236561,175399,892308,70536,382907,713705,12608,973798,673762,544544,822899,555617,880179,628081,187187,55039,337473,21538,905593,126951,635004,505333,180139,142110,333625,640335,322476,781082,41542,774131,781461,243942,764785,106325,78035,520993,412743,685724,679252,574610,236182,5960,527455,469856,468300,700388,579306,14157,434206,719040,689589,251914,724930,653264,226701,415923,838879,704372,130339,334296,814653,334088,790990,94098,501140,47317,939092,77880,354085,165182,176451,38447,205822,774420,311645,626304,149952,684801,687549,896784,26780,193029,276090,735515,427797,151976,787264,533611,378712,727390,352205,342086,822416,870374,497603,500388,899771,323454,499704,838211,410944,875458,285947,727461,646388,839484,111544,138154,608612,63932,352295,746987,651192,399906,728970,395682,171114,84270,495867,839907,492230,138260,908515,937549,427962,351953,894552,774593,290263,646676,241085,43944,113287,19154,893772,885278,671417,106906,965458,318901,861611,149816,916340,392909,412059,522164,947098,877726,497599,519588,399419,458375,468679,814743,979380,286231,225808,325705,754481,626122,208922,480062,312529,395348,967555,837100,144895,642938,674678,712795,900595,821413,113828,888544,959956,717353,500180,782043,201122,138656,567317,180262,471424,392480,480760,964973,62189,522309,395372,944802,86059,215322,639917,178327,601856,159902,732802,893015,290818,146217,493169,426085,308666,722400,916820,307549,411192,764822,701653,157114,892058,980127,34315,550009,542563,268410,980381,2107,441544,960600,552350,159580,859585,15155,688493,877479,963019,775171,51745,588739,159021,761601,104697,533623,185493,735321,86274,267021,267562,476639,531408,146690,38236,25546,621706,812591,964966,552651,764186,254845,34032,207582,365036,246579,267417,904773,630466,815164,168587,659893,124968,79141,358233,855532,662757,186068,382829,986399,54657,433345,759009,692811,334574,760233,240663,746478,479278,191441,737975,204782,746501,817716,268398,538691,661611,463748,26066,460385,172748,954729,683655,440531,420291,415040,99866,287903,176648,598940,646356,471767,906367,580559,321896,45861,270873,232886,959177,716452,644850,919860,801040,957651,644173,253228,480840,892822,625119,216961,151266,485379,552244,72861,782258,525044,899970,471038,602854,457874,428806,462820,172614,676225,555013,61065,984106,697956,814469,576356,818537,628903,425758,756515,984801,84909,601563,558901,949595,908436,398770,434619,543101,354428,184755,492378,859957,683234,981569,792905,245839,878452,479728,743298,2629,914252,126191,246900,674023,315634,838718,611904,993845,914695,347725,660614,208380,302514,748168,425130,399825,950873,700531,910266,615276,35760,809526,188209,709624,420305,183362,705543,137022,109181,564182,938406,117430,880963,360050,973645,715724,23120,555918,451510,120027,557538,246438,752089,919102,871268,521774,812109,861433,448727,765191,275124,263421,678492,691506,805005,910937,639494,988677,266566,485751,811893,77835,346886,882895,125414,749626,203688,880568,556998,398264,136118,190458,331400,961925,891659,278778,218911,101066,406780,878773,547582,694771,989097,929576,877025,420137,989364,177343,622642,519760,166910,31433,61958,844208,853417,244349,499032,688960,146565,381347,479481,819139,507499,969838,894333,9732,721274,343645,875397,484052,119838,222999,627816,375216,999514,238632,299221,237463,744668,511305,530034,728385,844981,593369,307272,106008,768361,623551,306707,208349,383923,811664,284169,62474,51441,219984,35061,305095,984874,870828,1392,939053,830408,208144,2908,459348,411452,651880,911442,938634,81494,333607,630177,490140,989032,351510,260933,87164,627269,845235,907200,278170,594936,377188,737722,854310,240878,277696,114767,539543,315074,642737,254576,999928,5550,807960,211166,156949,71651,922053,106322,440094,587884,148519,975709,172372,189620,826155,862590,138510,101055,183444,783627,216546,245986,176655,72059,555964,597975,625881,476864,69163,575383,178877,64015,971949,996504,239466,32590,137504,430799,652439,24132,375810,108211,693605,146369,966261,485408,705012,134033,925230,909986,945966,934575,744916,927278,837036,448,201152,206870,275385,946102,255185,444053,919316,291752,265899,331994,17370,733367,276578,437177,593137,38473,205762,79392,150147,204124,686502,268654,23845,606166,723414,968832,597157,10018,370042,41013,102136,833339,638904,735529,22364,169360,892914,912431,744608,154952,205226,789951,500289,832946,790471,317783,49914,449837,169347,489722,407525,534922,222583,265843,554476,266723,212029,374002,450375,482489,419225,492603,480241,206429,10631,28453,599235,107214,914528,868235,621970,142332,479782,556736,600570,843421,692591,546829,605007,976960,955216,824567,522329,288089,311025,571442,551171,111045,66077,222908,50308,937582,307132,89566,133856,508841,895368,345746,283642,826450,379896,917752,124455,125013,328298,581765,81640,151245,132645,775888,158429,831173,314561,640438,241802,273602,103432,249962,63963,317059,424962,584630,796157,863214,37599,718161,392820,482299,109864,172150,705745,216545,812897,363106,934807,440470,679331,902425,339943,236509,575782,492734,559132,214672,144004,233809,718292,567730,953682,582285,386345,397584,960424,452964,222732,617729,590406,789508,801609,862765,74904,667290,275565,116982,864254,599971,720920,808148,38746,286759,764150,234878,744261,518613,155505,887987,434599,158772,631132,37575,913967,85054,246268,992151,645869,159592,689649,6005,65922,762971,763443,229160,377218,369863,598238,229218,963122,167200,923335,887925,328323,997267,482939,860973,143883,399466,5903,851210,141639,687777,470398,84980,663717,598249,390547,892178,87922,342816,800106,490838,710319,278424,969643,696477,452769,605133,454267,342482,910927,420898,15837,825656,610874,535252,379274,714806,799604,438325,667566,694993,516000,717235,219185,139284,113740,862532,81676,30639,776146,582259,108265,383327,531439,94879,92514,907036,744196,769134,104392,761365,685565,644796,279129,44031,767178,85179,525455,654174,992624,442100,265744,927423,768019,182824,697528,548680,387933,948949,452044,616951,11468,526099,853563,462828,577785,82505,137109,958596,493100,373659,3077,470979,23957,960087,242361,920468,717715,993601,979082,666009,323389,454970,534879,221235,999628,140250,143740,269357,245147,116465,171998,395253,860590,786851,425653,358522,997395,799038,609102,742494,428642,841607,59153,126065,462614,533577,94394,294900,44002,214198,859762,338839,862327,486438,704419,343365,512893,953168,463811,462172,778950,61164,84837,379815,381263,420349,172071,512288,719918,91799,122919,158153,454526,719423,619648,111663,699828,460138,804004,296757,749614,212850,199435,399338,759172,155733,850266,952172,749869,580124,425871,990417,881537,32588,7146,72309,648106,775222,121602,123645,163806,488946,962661,383440,175962,708520,792923,790677,33499,213134,178812,814237,717466,634354,424458,477730,745955,938639,467837,269793,314278]

n = gets.to_i
if n<214
    p f[n]
else
    p f[(n-214)%955+214]
end
	f=[0,1,2,6,42,1806,263433,731,535092,124587,998593,986687,302009,464463,695657,905495,640763,631204,925569,329302,811189,430832,86208,883179,689211,66699,809956,563811,453886,336846,224167,917306,690598,857430,856778,195861,612099,673908,303919,785382,820837,180090,490894,687202,859271,295677,921734,939717,330608,652369,687778,845951,793459,89412,571174,330733,319870,829822,315697,612514,887194,719497,99481,539154,702812,928327,361889,617321,691110,290314,256064,831456,837441,162004,379285,58939,854241,351144,89974,386365,851759,69364,419427,900002,70000,55300,136126,368412,362975,818350,531765,698671,400492,761377,958427,517016,259357,111008,850106,893308,682181,202832,899636,404103,148815,986605,492469,480855,318217,73520,247705,830659,134961,551840,23859,274033,133840,225701,14279,903511,581642,982888,905234,41649,675648,526055,558881,594001,723494,721204,370418,453515,691715,897536,352125,995777,854799,993163,778622,178753,717906,196578,990736,867767,175002,783131,106413,799013,657922,717426,238805,895749,759658,305385,23830,891029,188077,39887,7883,149386,259434,57872,216209,407652,62216,881262,264043,760738,329219,154025,783481,419319,315596,852012,122387,655222,236561,175399,892308,70536,382907,713705,12608,973798,673762,544544,822899,555617,880179,628081,187187,55039,337473,21538,905593,126951,635004,505333,180139,142110,333625,640335,322476,781082,41542,774131,781461,243942,764785,106325,78035,520993,412743,685724,679252,574610,236182,5960,527455,469856,468300,700388,579306,14157,434206,719040,689589,251914,724930,653264,226701,415923,838879,704372,130339,334296,814653,334088,790990,94098,501140,47317,939092,77880,354085,165182,176451,38447,205822,774420,311645,626304,149952,684801,687549,896784,26780,193029,276090,735515,427797,151976,787264,533611,378712,727390,352205,342086,822416,870374,497603,500388,899771,323454,499704,838211,410944,875458,285947,727461,646388,839484,111544,138154,608612,63932,352295,746987,651192,399906,728970,395682,171114,84270,495867,839907,492230,138260,908515,937549,427962,351953,894552,774593,290263,646676,241085,43944,113287,19154,893772,885278,671417,106906,965458,318901,861611,149816,916340,392909,412059,522164,947098,877726,497599,519588,399419,458375,468679,814743,979380,286231,225808,325705,754481,626122,208922,480062,312529,395348,967555,837100,144895,642938,674678,712795,900595,821413,113828,888544,959956,717353,500180,782043,201122,138656,567317,180262,471424,392480,480760,964973,62189,522309,395372,944802,86059,215322,639917,178327,601856,159902,732802,893015,290818,146217,493169,426085,308666,722400,916820,307549,411192,764822,701653,157114,892058,980127,34315,550009,542563,268410,980381,2107,441544,960600,552350,159580,859585,15155,688493,877479,963019,775171,51745,588739,159021,761601,104697,533623,185493,735321,86274,267021,267562,476639,531408,146690,38236,25546,621706,812591,964966,552651,764186,254845,34032,207582,365036,246579,267417,904773,630466,815164,168587,659893,124968,79141,358233,855532,662757,186068,382829,986399,54657,433345,759009,692811,334574,760233,240663,746478,479278,191441,737975,204782,746501,817716,268398,538691,661611,463748,26066,460385,172748,954729,683655,440531,420291,415040,99866,287903,176648,598940,646356,471767,906367,580559,321896,45861,270873,232886,959177,716452,644850,919860,801040,957651,644173,253228,480840,892822,625119,216961,151266,485379,552244,72861,782258,525044,899970,471038,602854,457874,428806,462820,172614,676225,555013,61065,984106,697956,814469,576356,818537,628903,425758,756515,984801,84909,601563,558901,949595,908436,398770,434619,543101,354428,184755,492378,859957,683234,981569,792905,245839,878452,479728,743298,2629,914252,126191,246900,674023,315634,838718,611904,993845,914695,347725,660614,208380,302514,748168,425130,399825,950873,700531,910266,615276,35760,809526,188209,709624,420305,183362,705543,137022,109181,564182,938406,117430,880963,360050,973645,715724,23120,555918,451510,120027,557538,246438,752089,919102,871268,521774,812109,861433,448727,765191,275124,263421,678492,691506,805005,910937,639494,988677,266566,485751,811893,77835,346886,882895,125414,749626,203688,880568,556998,398264,136118,190458,331400,961925,891659,278778,218911,101066,406780,878773,547582,694771,989097,929576,877025,420137,989364,177343,622642,519760,166910,31433,61958,844208,853417,244349,499032,688960,146565,381347,479481,819139,507499,969838,894333,9732,721274,343645,875397,484052,119838,222999,627816,375216,999514,238632,299221,237463,744668,511305,530034,728385,844981,593369,307272,106008,768361,623551,306707,208349,383923,811664,284169,62474,51441,219984,35061,305095,984874,870828,1392,939053,830408,208144,2908,459348,411452,651880,911442,938634,81494,333607,630177,490140,989032,351510,260933,87164,627269,845235,907200,278170,594936,377188,737722,854310,240878,277696,114767,539543,315074,642737,254576,999928,5550,807960,211166,156949,71651,922053,106322,440094,587884,148519,975709,172372,189620,826155,862590,138510,101055,183444,783627,216546,245986,176655,72059,555964,597975,625881,476864,69163,575383,178877,64015,971949,996504,239466,32590,137504,430799,652439,24132,375810,108211,693605,146369,966261,485408,705012,134033,925230,909986,945966,934575,744916,927278,837036,448,201152,206870,275385,946102,255185,444053,919316,291752,265899,331994,17370,733367,276578,437177,593137,38473,205762,79392,150147,204124,686502,268654,23845,606166,723414,968832,597157,10018,370042,41013,102136,833339,638904,735529,22364,169360,892914,912431,744608,154952,205226,789951,500289,832946,790471,317783,49914,449837,169347,489722,407525,534922,222583,265843,554476,266723,212029,374002,450375,482489,419225,492603,480241,206429,10631,28453,599235,107214,914528,868235,621970,142332,479782,556736,600570,843421,692591,546829,605007,976960,955216,824567,522329,288089,311025,571442,551171,111045,66077,222908,50308,937582,307132,89566,133856,508841,895368,345746,283642,826450,379896,917752,124455,125013,328298,581765,81640,151245,132645,775888,158429,831173,314561,640438,241802,273602,103432,249962,63963,317059,424962,584630,796157,863214,37599,718161,392820,482299,109864,172150,705745,216545,812897,363106,934807,440470,679331,902425,339943,236509,575782,492734,559132,214672,144004,233809,718292,567730,953682,582285,386345,397584,960424,452964,222732,617729,590406,789508,801609,862765,74904,667290,275565,116982,864254,599971,720920,808148,38746,286759,764150,234878,744261,518613,155505,887987,434599,158772,631132,37575,913967,85054,246268,992151,645869,159592,689649,6005,65922,762971,763443,229160,377218,369863,598238,229218,963122,167200,923335,887925,328323,997267,482939,860973,143883,399466,5903,851210,141639,687777,470398,84980,663717,598249,390547,892178,87922,342816,800106,490838,710319,278424,969643,696477,452769,605133,454267,342482,910927,420898,15837,825656,610874,535252,379274,714806,799604,438325,667566,694993,516000,717235,219185,139284,113740,862532,81676,30639,776146,582259,108265,383327,531439,94879,92514,907036,744196,769134,104392,761365,685565,644796,279129,44031,767178,85179,525455,654174,992624,442100,265744,927423,768019,182824,697528,548680,387933,948949,452044,616951,11468,526099,853563,462828,577785,82505,137109,958596,493100,373659,3077,470979,23957,960087,242361,920468,717715,993601,979082,666009,323389,454970,534879,221235,999628,140250,143740,269357,245147,116465,171998,395253,860590,786851,425653,358522,997395,799038,609102,742494,428642,841607,59153,126065,462614,533577,94394,294900,44002,214198,859762,338839,862327,486438,704419,343365,512893,953168,463811,462172,778950,61164,84837,379815,381263,420349,172071,512288,719918,91799,122919,158153,454526,719423,619648,111663,699828,460138,804004,296757,749614,212850,199435,399338,759172,155733,850266,952172,749869,580124,425871,990417,881537,32588,7146,72309,648106,775222,121602,123645,163806,488946,962661,383440,175962,708520,792923,790677,33499,213134,178812,814237,717466,634354,424458,477730,745955,938639,467837,269793,314278]

	n = gets.to_i
	if n<214
	p f[n]
	else
	p f[(n-214)%955+214]
	end