Detailed mathematical approach

Problem Summary

Start with an \(m \times m\) square and remove an \(n \times n\) square from the lower-right corner, where \(0 \le n \lt m\). The remaining gnomon has \(m^2-n^2\) cells. We must count the ways to place the integers \(1,2,\dots,m^2-n^2\) so that every row increases from left to right and every column increases from top to bottom, then evaluate the count modulo \(76543217\).

Mathematical Approach

Step 1: Write the Gnomon as a Partition

Let \(p=m-n\). As a Ferrers diagram, the gnomon is the partition

$\lambda=(\underbrace{m,\dots,m}_{p},\underbrace{p,\dots,p}_{n}).$

The first \(p\) rows have length \(m\), while the last \(n\) rows have length \(p\). Therefore the total number of cells is

$|\lambda|=pm+np=(m-n)m+n(m-n)=m^2-n^2.$

A valid numbering of the gnomon is exactly a standard Young tableau of this shape.

Step 2: Apply the Hook-Length Formula

If \(T(m,n)\) denotes the number of valid numberings, the Frame-Robinson-Thrall formula gives

$T(m,n)=\frac{(|\lambda|)!}{\prod_{u \in \lambda} h(u)},$

where \(h(u)\) is the hook length of cell \(u\): the number of cells to its right, plus the number below it, plus the cell itself.

So the problem reduces to evaluating the hook product for this particular gnomon shape.

Step 3: Split the Shape into Three Regions

Using \(1\)-based coordinates \((i,j)\), the diagram naturally splits into a \(p \times p\) corner square and two \(p \times n\) arms.

In the top-left square, both the row length and column length are \(m\). Hence

$h(i,j)=(m-j)+(m-i)+1=2m-i-j+1 \qquad (1 \le i,j \le p).$

In the top-right arm, write \(j=p+b\) with \(1 \le b \le n\). The row still has length \(m\), but the column length is only \(p\), so

$h(i,p+b)=(m-p-b)+(p-i)+1=m-i-b+1 \qquad (1 \le i \le p,\ 1 \le b \le n).$

In the bottom-left arm, write \(i=p+a\) with \(1 \le a \le n\). Now the row length is \(p\) and the column length is \(m\), giving

$h(p+a,j)=(p-j)+(m-p-a)+1=m-a-j+1 \qquad (1 \le a \le n,\ 1 \le j \le p).$

The last two formulas describe the same multiset of hook lengths, so the two arms contribute identical factors.

Step 4: Convert the Hook Product into Factorial Ratios

Let \(H\) be the product of all hook lengths. We write

$H=P_A \cdot P_B^2,$

where \(P_A\) is the contribution of the \(p \times p\) corner square and \(P_B\) is the contribution of one arm.

For the corner square, fix a row \(i\). As \(j\) runs from \(1\) to \(p\), the hooks are consecutive integers, so

$\prod_{j=1}^{p}(2m-i-j+1)=\frac{(2m-i)!}{(m+n-i)!}.$

Multiplying over all \(i=1,\dots,p\) gives

$P_A=\prod_{i=1}^{p}\frac{(2m-i)!}{(m+n-i)!} =\frac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}.$

For one arm, fixing \(i\) yields another consecutive block:

$\prod_{b=1}^{n}(m-i-b+1)=\frac{(m-i)!}{(p-i)!}.$

Therefore

$P_B=\prod_{i=1}^{p}\frac{(m-i)!}{(p-i)!} =\frac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}.$

The lower-left arm has the same hook multiset, so its contribution is another factor of \(P_B\).

Step 5: Final Closed Formula

Substituting the factorization of \(H\) into the hook-length formula yields

$\boxed{T(m,n)=\frac{(m^2-n^2)!}{\left(\dfrac{\prod_{t=m+n}^{2m-1} t!}{\prod_{s=2n}^{m+n-1} s!}\right)\left(\dfrac{\prod_{t=n}^{m-1} t!}{\prod_{u=0}^{p-1} u!}\right)^2}}.$

Here \(p=m-n\). This is exactly the product decomposition used by the C++, Python, and Java implementations.

Worked Example: \((m,n)=(5,3)\)

For \(m=5\) and \(n=3\), we have \(p=2\) and \(m^2-n^2=16\). The formulas above give

$P_A=\frac{8!\,9!}{6!\,7!}=4032,$

$P_B=\frac{3!\,4!}{0!\,1!}=144.$

Hence

$H=P_A P_B^2=4032 \cdot 144^2=83607552,$

and therefore

$T(5,3)=\frac{16!}{83607552}=250250.$

This matches the exact checkpoint used by the implementation. A second consistency check is

$T(10,5)\equiv 61251715 \pmod{76543217}.$

How the Code Works

The implementation follows the formula directly. It computes \((m^2-n^2)!\bmod M\), precomputes factorials up to \(2m-1\), evaluates the two short ratio blocks \(P_A\) and \(P_B\), multiplies them into the full hook product \(H\), and then replaces division by a modular inverse.

Since \(M=76543217\) is prime, Fermat's little theorem gives

$x^{-1}\equiv x^{M-2}\pmod{M}.$

So the final modular computation is

$T(m,n)\equiv (m^2-n^2)! \cdot H^{M-2}\pmod{M}.$

Complexity Analysis

The dominant cost is computing \((m^2-n^2)!\bmod M\), which takes \(O(m^2-n^2)\) modular multiplications. Building the factorial table up to \(2m-1\) and evaluating the two ratio blocks costs only \(O(m)\) time. The memory usage is \(O(m)\) because the implementation stores only the short factorial table.

References

1. Problem page: https://projecteuler.net/problem=412
2. Hook-length formula: Wikipedia — Hook-length formula
3. Standard Young tableaux: Wikipedia — Young tableau
4. Ferrers diagram: Wikipedia — Ferrers diagram
5. Frame, Robinson, Thrall (1954). The hook graphs of the symmetric group, Canadian Journal of Mathematics 6, 316-324.
6. Fermat's little theorem: Wikipedia — Fermat's little theorem