定义一个排列为“好排列”，当且仅当所有相邻两个数的乘积均为偶数。 小欧想知道，长度 的“好排列”一共有多少种？由于答案可能很大，请将答案对 取模后输出。 长度为 的排列是由 这 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， 是一个长度为 的排列，而 和 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

一个正整数。

输出描述:

输出一个整数，代表“好排列”的数量。由于答案可能很大，请将答案对  取模后输出。