ZCMU 暑期训练四---L题

You have a given integer nn. Find the number of ways to fill all 3×n3×n tiles with the shape described in the picture below. Upon filling, no empty spaces are allowed. Shapes cannot overlap.

This picture describes when n=4n=4. The left one is the shape and the right one is 3×n3×n tiles.

Input

The only line contains one integer nn (1≤n≤601≤n≤60) — the length.

Output

Print the number of ways to fill.

Examples

Input

4

Output

4

Input

1

Output

0

Note

In the first example, there are 44 possible cases of filling.

In the second example, you cannot fill the shapes in 3×13×1 tiles.

【题解】

找规律  找到公式就可以了；

#include<cstdio> #include<cmath> #include<iostream> #include<vector> #include<cstring> using namespace std; int main(){ int n,ans=1; cin>>n; if(n%2==1){ cout<<"0"<<endl; }else { for (int i=1;i<=n/2;i++) ans=ans* 2; cout <<ans<< endl; } return 0; }