中南大学第十一届大学生程序设计竞赛-COJ1895-Apache is late again

22℃

[隐藏]

1.1895: Apache is late again

Submit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 7 Solved: 3

Description

Apache is a student of CSU. There is a math class every Sunday morning, but he is a very hard man who learns late every night. Unfortunate, he was late for maths on Monday. Last week the math teacher gave a question to let him answer as a punishment, but he was easily resolved. So the math teacher prepared a problem for him to solve. Although Apache is very smart, but also was stumped. So he wants to ask you to solve the problem. Questions are as follows: You can find a m made (1 + sqrt (2)) ^ n can be decomposed into sqrt (m) + sqrt (m-1), if you can output m% 100,000,007 otherwise output No.

Input

There are multiply cases. Each case is a line of n. (|n| <= 10 ^ 18)

Output

Line, if there is no such m output No, otherwise output m% 100,000,007.

Sample Input

2

Sample Output

9

Hint

Source

(1+2)n=m+m1$(1+\sqrt{2})^n=\sqrt{m}+\sqrt{m-1}$

(1+2)1=2+1=12+1+12$(1+\sqrt{2})^1=\sqrt{2}+\sqrt{1}=\sqrt{1^2+1}+\sqrt{1^2}$

(1+2)2=9+8=32+321$(1+\sqrt{2})^2=\sqrt{9}+\sqrt{8}=\sqrt{3^2}+\sqrt{3^2-1}$

(1+2)3=50+49=72+1+72$(1+\sqrt{2})^3=\sqrt{50}+\sqrt{49}=\sqrt{7^2+1}+\sqrt{7^2}$

(1+2)4=289+288=172+1721$(1+\sqrt{2})^4=\sqrt{289}+\sqrt{288}=\sqrt{17^2}+\sqrt{17^2-1}$

(1+2)5=1682+1681=412+1+412$(1+\sqrt{2})^5=\sqrt{1682}+\sqrt{1681}=\sqrt{41^2+1}+\sqrt{41^2}$

$\dots$

a1=1,a2=3,a3=7,a4=17,a5=41,$a_1=1,a_2=3,a_3=7,a_4=17,a_5=41,\cdots$

an=2an1+an2$a_n=2*a_{n-1}+a_{n-2}$

[anan1]=[2110][an1an2]=[2110]n2[a2a1]$\begin{bmatrix} a_n \\ a_{n-1} \\ \end{bmatrix}=\begin{bmatrix} 2&1 \\1&0 \end{bmatrix}\begin{bmatrix} a_{n-1}\\ a_{n-2}\end{bmatrix}={\begin{bmatrix} 2&1\\ 1&0\end{bmatrix} }^{n-2}\begin{bmatrix}a_2\\ a_1 \end{bmatrix}$

#include
#include
using namespace std;
typedef long long LL;
const int MOD=1e8+7;

struct matrix
{
LL v[2][2];
matrix(){memset(v,0,sizeof(v));}
matrix operator * (const matrix &m)
{
matrix c;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
c.v[i][j]+=(v[i][k]*m.v[k][j])%MOD;
return c;
}
};

matrix M,E,ans;//E为单位矩阵,ans为M^(n-2)

void Init()//初始化
{
for(int i=0;i<2;i++)
E.v[i][i]=1;
M.v[0][0]=2;M.v[0][1]=1;
M.v[1][0]=1;M.v[1][1]=0;
}

matrix pow(matrix p,LL k)
{
matrix tmp=E;
while(k)
{
if(k&1)
{
tmp=tmp*p;
k--;
}
k>>=1;
p=p*p;
}
return tmp;
}

int main()
{
ios::sync_with_stdio(false);
LL n;
Init();
while(cin>>n)
{
if(n<0) cout<<"No"<else if(n==0) cout<<"1"<else if(n==1) cout<<"2"<else if(n==2) cout<<"9"<else
{
ans=pow(M,n-2);
LL an=(ans.v[0][0]*3+ans.v[0][1]*1)%MOD;
if(n&1) cout<<((an*an)%MOD+1)%MOD<else cout<<(an*an)%MOD<return 0;
}