答案就是卡特兰数

证明：依次考虑1~2n中的每个数，挨个放入序列中的某个位置（可以选奇数位置或者是偶数位置），要求中间的任何时候选的奇数位置的个数>=偶数位置的个数，走的方案数就是卡特兰数。 卡特兰数计算公式C(2n, n)/ (n+1)

mod p的p是任给的，所以模数和除数不一定互质，不互质一定无法进行乘法逆元的运算

所以考察的是第n项卡特兰数模p