Description

N+Q是班长。在校运动会上，N+Q班要进行队列表演。N+Q要选出2*N名同学编队，每人都被编上一个号，每一个从1到N的自然数都被某2名同学佩戴，现在要求将他们排成一列，使两个编号为1的同学中间恰好夹1名同学，两个编号为2的同学中间恰好夹2名同学，……，两个编号为N的同学中间恰好夹N名同学，N+Q希望知道这样的排法能否实现。

Format

Input

仅包括一行，即要处理的N。 1<=N<=13

Output

输出有多少种合法的排列方式。

Samples

【输入样例】

3

【输出样例】

2

Limitation

1s, 1024KiB for each test case.