Problem 916

Restricted Permutations

Let $P (n)$ be the number of permutations of ${1, 2, 3, \dots, 2 n}$ such that:

There is no ascending subsequence with more than $n + 1$ elements, and
There is no descending subsequence with more than two elements.

Note that subsequences need not be contiguous. For example, the permutation $(4, 1, 3, 2)$ is not counted because it has a descending subsequence of three elements: $(4, 3, 2)$ . You are given $P (2) = 13$ and $P (10) \equiv 45265702 (\mod 10^{9} + 7)$ .

Find $P (10^{8})$ and give your answer modulo $10^{9} + 7$ .

有限制排列

令 $P (n)$ 为满足以下条件的 ${1, 2, 3, \dots, 2 n}$ 的排列的数量：

不存在长度超过 $n + 1$ 的递增子序列，且
不存在长度超过 $2$ 的递减子序列。

注意子序列不必连续。例如，排列 $(4, 1, 3, 2)$ 不符合条件，因为它有一个长度为 $3$ 的递减子序列： $(4, 3, 2)$ 。已知 $P (2) = 13$ ， $P (10) \equiv 45265702 (\mod 10^{9} + 7)$ 。

求 $P (10^{8})$ ，并对 $10^{9} + 7$ 取余作为你的答案。