Problem 907

Stacking Cups

An infant’s toy consists of $n$ cups, labelled $C_{1}, \dots, 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}, \dots, 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$ 取余作为你的答案。