设 $(p_1{p}_2\dots p_k)$ 表示将 $p_i\mapsto i$ 的集合 $1,...,k$ 的排列。定义排列的长度为$k$；请注意，空排列 $()$ 的长度为零。

将排列 $P=(P_1{P}_2\cdots P_n)$ 中排列 $p=(p_1{p}_2\cdots p_k)$ 的出现定义为序列 $1\le t_1<t_2<\cdots <t_k\le n$，使得 $p_i<p_j$ 如果和仅当 $P_{t_i}<P_{t_j}$ 对于所有 $i,j\in \{1,\dots ,k\}$ 时。

例如，$(1243)$ 在排列 $(314625)$ 中出现两次：一次作为第 1、3、4 和 6 个元素 $(3465)$，一次作为第 2、3、4 和 6 个元素 $(1465)$。

令 $f(n,m)$ 为长度至多为 $n$ 的排列 $P$ 的数量，使得 $P$ 中不会出现排列 $1243$，并且 $P$ 中最多出现 $m$ 排列 $21$。

例如，$f(2,0)=3$，排列为 $()$、$(1)$、$(1,2)$，但不是 $(2,1)$。

您还得到 $f(4,5)=32$ 和 $f(10,25)=294400$。

求 $f({10}^{18},40)$ 模 $1000000007$。