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

输入描述:

输入一个整数 代表排列的长度。

输出描述:

输出一个整数，代表长度为 的双生排列数量对 取模的答案。