Given a permutation of length , Alice uses the inversion number as a measure of how close is to the permutation , while Bob uses the metric .
Here, the inversion number is the number of pairs such that and .
Given a sequence of length , there are permutations of length that have as their prefix.
Find the number of these permutations for which Alice's metric and Bob's metric are equal, and return the result modulo .
