Let $(p_1{p}_2\dots p_k)$ denote the permutation of the set $1,...,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\cdots p_k)$ in a permutation $P=(P_1{P}_2\cdots P_n)$ to be a sequence $1\le t_1<t_2<\cdots <t_k\le 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 $(3465)$, and once as the 2nd, 3rd, 4th and 6th elements $(1465)$.

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)=294400$.

Find $f({10}^{18},40)$ modulo $1000000007$.