#include <cstring>
using namespace std;
int mat[ 9 ] [ 9 ] = // constructing matrix column by column
{ { 0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 } ,
{ 4 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 } ,
{ 0 ,2 ,0 ,0 ,0 ,0 ,0 ,1 ,0 } ,
{ 0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,2 ,2 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,1 } ,
{ 0 ,0 ,0 ,0 ,2 ,2 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 } } ;
int one[ 9 ] [ 9 ] = //
{ { 1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 } } ;
int zero[ 9 ] [ 9 ] = //
{ { 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } ,
{ 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 } } ;
const int mod = 1000000007 ;
class matrix { public :
int a[ 9 ] [ 9 ] ;
void take( int mt[ 9 ] [ 9 ] )
{
for ( int i= 0 ; i< 9 ; ++ i)
for ( int j= 0 ; j< 9 ; ++ j)
a[ i] [ j] = mt[ i] [ j] ;
}
void operator = ( matrix b)
{
for ( int i= 0 ; i< 9 ; ++ i)
for ( int j= 0 ; j< 9 ; ++ j)
a[ i] [ j] = b.a [ i] [ j] ;
}
matrix operator * ( matrix b)
{
matrix c; c.take ( zero) ;
for ( int i= 0 ; i< 9 ; ++ i)
for ( int j= 0 ; j< 9 ; ++ j)
for ( int k= 0 ; k< 9 ; ++ k)
c.a [ i] [ j] = ( 1LL * c.a [ i] [ j] + 1LL * a[ i] [ k] * b.a [ k] [ j] ) % mod;
return c;
}
} ;
matrix pow ( matrix a,long long pw)
{
if ( pw == 0 )
{
matrix out;
out.take ( one) ;
return out;
}
matrix out = pow ( a,pw/ 2 ) ;
out = out * out;
if ( pw % 2 ) out = out * a;
return out;
}
class Chimney { public :
int countWays( long long n)
{
matrix a; a.take ( mat) ;
matrix b = pow ( a,n* 4 ) ;
return b.a [ 0 ] [ 0 ] ;
}
} ;
I2luY2x1ZGUgPGNzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWF0WzldWzldID0gIC8vIGNvbnN0cnVjdGluZyBtYXRyaXggY29sdW1uIGJ5IGNvbHVtbgoge3swLDAsMCwwLDEsMCwwLDAsMH0sCiAgezQsMCwwLDAsMCwwLDEsMCwwfSwKICB7MCwyLDAsMCwwLDAsMCwxLDB9LAogIHswLDEsMCwwLDAsMCwwLDAsMH0sCiAgezAsMCwyLDIsMCwwLDAsMCwwfSwKICB7MCwwLDEsMCwwLDAsMCwwLDF9LAogIHswLDAsMCwwLDIsMiwwLDAsMH0sCiAgezAsMCwwLDAsMCwwLDEsMCwwfSwKICB7MCwwLDAsMCwwLDAsMCwxLDB9fTsKICAKaW50IG9uZVs5XVs5XSA9ICAvLyAKIHt7MSwwLDAsMCwwLDAsMCwwLDB9LAogIHswLDEsMCwwLDAsMCwwLDAsMH0sCiAgezAsMCwxLDAsMCwwLDAsMCwwfSwKICB7MCwwLDAsMSwwLDAsMCwwLDB9LAogIHswLDAsMCwwLDEsMCwwLDAsMH0sCiAgezAsMCwwLDAsMCwxLDAsMCwwfSwKICB7MCwwLDAsMCwwLDAsMSwwLDB9LAogIHswLDAsMCwwLDAsMCwwLDEsMH0sCiAgezAsMCwwLDAsMCwwLDAsMCwxfX07CiAgCmludCB6ZXJvWzldWzldID0gIC8vIAoge3swLDAsMCwwLDAsMCwwLDAsMH0sCiAgezAsMCwwLDAsMCwwLDAsMCwwfSwKICB7MCwwLDAsMCwwLDAsMCwwLDB9LAogIHswLDAsMCwwLDAsMCwwLDAsMH0sCiAgezAsMCwwLDAsMCwwLDAsMCwwfSwKICB7MCwwLDAsMCwwLDAsMCwwLDB9LAogIHswLDAsMCwwLDAsMCwwLDAsMH0sCiAgezAsMCwwLDAsMCwwLDAsMCwwfSwKICB7MCwwLDAsMCwwLDAsMCwwLDB9fTsKCgpjb25zdCBpbnQgbW9kID0gMTAwMDAwMDAwNzsKCmNsYXNzIG1hdHJpeCB7IHB1YmxpYzoKCWludCBhWzldWzldOwoJCgl2b2lkIHRha2UoaW50IG10WzldWzldKQoJewoJCWZvciAoaW50IGk9MDtpPDk7KytpKQoJCQlmb3IgKGludCBqPTA7ajw5OysraikJCgkJCQlhW2ldW2pdID0gbXRbaV1bal07Cgl9CgkKCXZvaWQgb3BlcmF0b3IgPSAobWF0cml4IGIpCgl7CgkJZm9yIChpbnQgaT0wO2k8OTsrK2kpCgkJCWZvciAoaW50IGo9MDtqPDk7KytqKQkKCQkJCWFbaV1bal0gPSBiLmFbaV1bal07Cgl9CgkKCW1hdHJpeCBvcGVyYXRvciAqIChtYXRyaXggYikKCXsKCQltYXRyaXggYzsgYy50YWtlKHplcm8pOwoJCWZvciAoaW50IGk9MDtpPDk7KytpKQoJCQlmb3IgKGludCBqPTA7ajw5OysraikKCQkJCWZvciAoaW50IGs9MDtrPDk7KytrKQoJCQkJCWMuYVtpXVtqXSA9ICggIDFMTCAqIGMuYVtpXVtqXSArIDFMTCAqIGFbaV1ba10gKiBiLmFba11bal0gKSAlIG1vZDsKCQlyZXR1cm4gYzsKCX0KfTsgCgptYXRyaXggcG93KG1hdHJpeCBhLGxvbmcgbG9uZyBwdykKewoJaWYgKCBwdyA9PSAwICkgCgl7CgkJbWF0cml4IG91dDsKCQlvdXQudGFrZShvbmUpOwoJCXJldHVybiBvdXQ7Cgl9CgkKCW1hdHJpeCBvdXQgPSBwb3coYSxwdy8yKTsKCW91dCA9IG91dCAqIG91dDsKCWlmICggcHcgJSAyICkgb3V0ID0gb3V0ICogYTsKCQoJcmV0dXJuIG91dDsKfQoKY2xhc3MgQ2hpbW5leSB7IHB1YmxpYzoKCWludCBjb3VudFdheXMobG9uZyBsb25nIG4pCgl7CgkJbWF0cml4IGE7IGEudGFrZShtYXQpOwoJCW1hdHJpeCBiID0gcG93KGEsbio0KTsKCQlyZXR1cm4gYi5hWzBdWzBdOwoJfQp9OwoK