给定满足$0\le n< m$的整数m,n，用$L(m, n)$表示在$m\times m$的方格中挖去右上角$n\times n$的子方格后留下的L型部分。

例如下图是$L(5, 3)$：

给$L(m, n)$中每一格连续地填入整数1, 2, 3, ...，要求每个格子中的数小于其左侧和下方格子中的数。

例如，下图是$L(5, 3)$中两种可行的填法：

记$LC(m, n)$为$L(m, n)$中所有可行填法的总数。

可以验证$LC(3,0)=42, LC(5,3)=250250, LC(6,3)=406029023400, LC(10,5)\bmod 76543217=61251715$。

求$LC(10000, 5000) \bmod 76543217$。

本题难度:

解答

本题即求所谓的杨表（Young Tableau）个数，可以参考此处。

用页面上的钩长公式直接计算即得结果$38788800$。

m=76543217

h=[0]*20000
for i in range(2,5001):
    h[i]=2*i
for i in range(5001,10000):
    h[i]=20000-2*i
for i in range(10001,15001):
    h[i]=i-10000
for i in range(15001,20000):
    h[i]=20000-i

d=f=1
for i in range(2,20000):
    d=(d*pow(i,h[i],m))%m
for i in range(m-1,75000000,-1):
    f=(f*i)%m

print ((m-pow(f,m-2,m))*pow(d,m-2,m))%m