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

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

Input

The only line contains one integer n (1 ≤ 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 4 possible cases of filling.

In the second example, you cannot fill the shapes in 3 × 1 tiles.
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long inf = 0x3f3f3f3f;
const long long nax = 0;
int n;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie();
  cout.tie();
  cin >> n;
  vector<long long> f(65);
  f[1] = 0;
  f[2] = 2;
  for (int i = 3; i <= n; ++i) {
    f[i] = 2 * f[i - 2];
  }
  cout << f[n] << '\n';
}
