Constrained Permutations
Problem 631
Let denote the permutation of the set that maps . Define the length of the permutation to be ; note that the empty permutation has length zero.
Define an occurrence of a permutation in a permutation to be a sequence such that if and only if for all .
For example, occurs twice in the permutation : once as the 1st, 3rd, 4th and 6th elements , and once as the 2nd, 3rd, 4th and 6th elements .
Let be the number of permutations of length at most such that there is no occurrence of the permutation in and there are at most occurrences of the permutation in .
For example, , with the permutations , , but not .
You are also given that and .
Find modulo .