题目

• 小聂定义了一种“双生排列”，即一个排列中任意相邻两项之和均为奇数。排列是由 1 到 n 这 n 个整数按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{2,3,1,5,4} 是一个长度为 5 的排列，而 {1,2,2} 不是排列（存在重复元素），{1,3,4} 也不是排列（元素不完整）。
• 已知排列的长度为 n（2 ≤ n ≤ 10⁵），求长度为 n 的双生排列的数量，由于结果可能很大，需对 10⁹ + 7 取模。

输入描述

• 在一行中输入一个整数 n，范围为 2 ≤ n ≤ 10⁵，代表排列的长度。

输出描述

• 输出一个整数，代表长度为 n 的双生排列数量对 10⁹ + 7 取模的结果。

示例 1

• 输入：

  3
  

• 输出：

  2
  

• 说明：
  • 长度为 3 的排列有 {1,2,3}、{1,3,2}、{2,1,3}、{2,3,1}、{3,1,2}、{3,2,1}。其中 {1,2,3} 和 {3,2,1} 是双生排列，所以长度为 3 的双生排列数量为 2。