因为套路与 OI 题略有不同，故放在此区。
给你 $n\times n$ 的网格，向其中不重复地填入 $1\sim n^2$ 这些正整数。要求：
1)对于左右相邻的两个格子，右边格子的数必须大于左边格子。
2)对于上下相邻的两个格子，下边格子的数必须大于上边格子。
求：合法的方案数。
目前进度： 显然可知左上角的格子的数为 $1$，右下角的格子的数为 $n^2$ 。 同学推测是卡特兰数套卡特兰数，但是具体不太确定。
求巨佬给出推导过程（若猜想正确），或能较快求出方案数的程序。