Problem 631

Constrained Permutations

Let $(p_{1} p_{2} \dots p_{k})$ denote the permutation of the set $1, \dots, k$ that maps $p_{i} \mapsto i$ . Define the length of the permutation to be $k$ ; note that the empty permutation $()$ has length zero.

Define an occurrence of a permutation $p = (p_{1} p_{2} \dots p_{k})$ in a permutation $P = (P_{1} P_{2} \dots P_{n})$ to be a sequence $1 \leq t_{1} < t_{2} < \dots < t_{k} \leq n$ such that $p_{i} < p_{j}$ if and only if $P_{t_{i}} < P_{t_{j}}$ for all $i, j \in 1, \dots, k$ .

For example, $(1243)$ occurs twice in the permutation $(314625)$ : once as the 1st, 3rd, 4th and 6th elements $(3 46 5)$ , and once as the 2nd, 3rd, 4th and 6th elements $(146 5)$ .

Let $f (n, m)$ be the number of permutations $P$ of length at most $n$ such that there is no occurrence of the permutation $(1243)$ in $P$ and there are at most $m$ occurrences of the permutation $(21)$ in $P$ .

For example, $f (2, 0) = 3$ , with the permutations $()$ , $(1)$ , $(1, 2)$ but not $(2, 1)$ .

You are also given that $f (4, 5) = 32$ and $f (10, 25) = 294 400$ .

Find $f (10^{18}, 40)$ modulo $1 000 000 007$ .

带约束的排列

用 $(p_{1} p_{2} \dots p_{k})$ 表示将集合 $1, \dots, k$ 按照 $p_{i} \mapsto i$ 映射的排列。记这样的排列的长度为 $k$ ；注意空排列 $()$ 的长度视为0。

考虑排列 $P = (P_{1} P_{2} \dots P_{n})$ 和较短的排列 $p = (p_{1} p_{2} \dots p_{k})$ ，如果存在序列 $1 \leq t_{1} < t_{2} < \dots < t_{k} \leq n$ ，使得对任意 $i, j \in 1, \dots, k$ ， $p_{i} < p_{j}$ 当且仅当 $P_{t_{i}} < P_{t_{j}}$ ，则称 $p$ 在 $P$ 中出现了一次。

例如，排列 $(1243)$ 在排列 $(314625)$ 中出现了两次：第一次由第1、3、4、6个元素组成，即 $(3 46 5)$ ；第二次由第2、3、4、6个元素组成，即 $(146 5)$ 。

考虑所有长度不超过 $n$ 的排列 $P$ ，其中，没有排列 $(1243)$ 出现，且排列 $(21)$ 出现至多 $m$ 次的排列总数记为 $f (n, m)$ 。

例如， $f (2, 0) = 3$ ，这三种排列分别是 $()$ ， $(1)$ 和 $(1, 2)$ ，而 $(2, 1)$ 不满足要求。

已知 $f (4, 5) = 32$ ，以及 $f (10, 25) = 294 400$ 。

求 $f (10^{18}, 40)$ 并对 $1 000 000 007$ 取余。