Rhodoks 喜欢有序而 AquaMoon 喜欢乱序。
AquaMoon 新买了 n 件衣服，它们按次序编号为 0,1,2,…,n−1 ，Rhodoks 把它们按编号顺序挂在了衣帽间，但是 AquaMoon 想乱序挂，乱序之后编号为 i 的衣服在位置 pi，p0,p1,...,pn−1是一个排列。她觉得这样更有美感。
最终，Rhodoks 决定，令 bi=∣pi−i∣ ，其中∣x∣代表x的绝对值。AquaMoon 挂的时候必须让 b0,b1,…,bn−1 也是一个排列。
AquaMoon 非常恼火，但是可怜的她没有话语权，所以她希望你能帮她算出来有多少种方案可以满足。
一个长度为n的数列是排列如果：0 到 n−1 这 n 个整数每个恰好出现一次。
两种方案被认为不同，如果存在某件衣服悬挂的位置在两个方案中不同。