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;
 }

最后

以上就是醉熏河马最近收集整理的关于ZCMU 暑期训练四---L题的全部内容，更多相关ZCMU内容请搜索靠谱客的其他文章。