---

Problem 907

---

Stacking Cups

An infant’s toy consists of $n$ cups, labelled $C_1,\ldots,C_n$ in increasing order of size.

The cups may be stacked in various combinations and orientations to form towers. The cups are shaped such that the following means of stacking are possible:

• Nesting: $C_k$ may sit snugly inside $C_{k+1}$.
• Base-to-base: $C_{k+2}$ or $C_{k-2}$ may sit, right-way-up, on top of an up-side-down $C_k$, with their bottoms fitting together snugly.
• Rim-to-rim: $C_{k+2}$ or $C_{k-2}$ may sit, up-side-down, on top of a right-way-up $C_k$, with their tops fitting together snugly.

Define $S(n)$ to be the number of ways to build a single tower using all $n$ cups according to the above rules.

You are given $S(4)=12$, $S(8)=58$, and $S(20)=5560$.

Find $S(10^7)$, giving your answer modulo $1\ 000\ 000\ 007$.

---

叠杯子

某种婴儿玩具包含$n$个杯子，按大小递增顺序依次记为$C_1,\ldots,C_n$。

这些杯子可以用多种方式进行堆叠。具体来说，杯子的形状被设计为允许采用如下的堆叠方式：

• 嵌套：$C_k$可以紧密地嵌套在$C_{k+1}$里面。
• 底对底：正放的$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)$，并对$1\ 000\ 000\ 007$取余作为你的答案。

---