---

Problem 798

---

Card Stacking Game

Two players play a game with a deck of cards which contains $s$ suits with each suit containing $n$ cards numbered from $1$ to $n$.

Before the game starts, a set of cards (which may be empty) is picked from the deck and placed face-up on the table, with no overlap. These are called the visible cards.

The players then make moves in turn.
A move consists of choosing a card X from the rest of the deck and placing it face-up on top of a visible card Y, subject to the following restrictions:

• X and Y must be the same suit;
• the value of X must be larger than the value of Y.

The card X then covers the card Y and replaces Y as a visible card.
The player unable to make a valid move loses and play stops.

Let $C(n,s)$ be the number of different initial sets of cards for which the first player will lose given best play for both players.

For example, $C(3,2)=26$ and $C(13,4)\equiv 540318329(\mathrm{mod}1000000007)$.

Find $C({10}^7,{10}^7)$. Give your answer modulo $1000000007$.

---

叠卡游戏

两位玩家正在玩一个游戏，这个游戏需要用到一副有$n$个花色、每个花色包含$1$到$n$共$n$种点数的牌。

在游戏开始前，从这副牌中拿出一部分（可以不拿），并将其面朝上互不接触地放在桌面上。这些牌被称为可见牌。

此后，两名玩家轮流行动。每一轮行动，玩家必须从剩下的牌中选择一张牌X，并将其面朝上放在一张可见牌Y上，且X和Y需要满足：

• X和Y的花色必须相同；
• X的点数必须大于Y的点数。

X会完全覆盖Y并取代Y成为可见牌。
首先无法进行合法行动的玩家失败，游戏结束。

若两位玩家均采取最优策略，记$C(n,s)$为先手玩家必败的可见牌布置局面的数目。

例如，$C(3,2)=26$，$C(13,4)\equiv 540318329(\mathrm{mod}1000000007)$。

求$C({10}^7,{10}^7)$，并将你的答案对$1000000007$取余。

---