婴儿玩具由 $n$ 个杯子组成，按尺寸递增顺序标记为 $C_1,\dots ,C_n$。

杯子可以以各种组合和方向堆叠以形成塔。杯子的形状使得可以采用以下堆叠方式：

• 嵌套：$C_k$ 可以紧贴在 $C_{k+1}$ 内部。
  
• 底座到底座：$C_{k+2}$ 或 $C_{k-2}$ 可以正确放置在颠倒的 $C_k$ 顶部，并且它们的底部紧密贴合。
  
• 边缘到边缘：$C_{k+2}$ 或 $C_{k-2}$ 可以倒置，位于右侧向上的 $C_k$ 顶部，其顶部紧密贴合。
  
• 就本问题而言，不允许将两者 $C_{k+2}$ 和 $C_{k-2}$ 边缘对边缘堆叠在 $C_k$ 之上，尽管示意图似乎允许这样做：
  
  

将$S(n)$定义为根据上述规则使用所有$n$个杯子建造单个塔的方法数。
给定 $S(4)=12$、$S(8)=58$ 和 $S(20)=5560$。

求 $S({10}^7)$，将答案模 $1000000007$ 给出。