将下面的 $6\times 4$ 方格表（如图）里 $24$ 个格子中的 $12$ 个涂上阴影，使得每一行恰有两个涂了阴影的方格，每一列恰有三个涂了阴影的方格。设 $N$ 是满足这样要求的涂阴影的方法数，求 $N$ 被1000除所有的余数。
【难度】
【出处】
2007年第25届美国数学邀请赛Ⅰ（AIMEⅠ）
【标注】
【答案】
860
【解析】
显然将左起第一列的六个方格中的三个打上阴影有 $C_{6}^{3}=20$ 种方法，下面不妨设左起第一列的上方三个格都有阴影，而下方三个格都没有阴影。考虑上方三行另一个阴影格的位置，分三种情况。
若上方三行剩余的一个阴影格的所在列完全相同，则这个列有 $C_{3}^{1}=3$ 种选择方式，而这个列选好后，下方三行的阴影格也只有唯一的选取方式，此时有 $3$ 种涂阴影的方法。
若上方三行剩余的一个阴影格中，有两个所在的列相同，另一个所在的列不同，则先选取有两个阴影格的列，有 $C_{3}^{1}=3$ 种选择方式，再选取一个阴影格的列，有 $C_{2}^{1}=2$ 种选择方式，最后选取单独的阴影格所在行，有 $C_{3}^{1}=3$ 种选择方式，故这样的前三行有 $3\times 3\times 2=18$ 种涂阴影的方法。当前三行确定后，还有一列没有阴影格，故这一列的后 $3$ 个格子必须都是涂阴影的，另外的两列中，有一列差 $1$ 个阴影格，另一列差 $2$ 个阴影格，这三个阴影格必须在这两列与三行的公共部分中选出，易知这样的选法有 $C_{3}^{1}=3$ 种，因此此时有 $18\times 3=54$ 种涂阴影的方法。
若上方三行剩余的阴影格所在的列都不同，则选定它们所在的列（此即选定它们的位置）有 $3!=6$ 种涂阴影的方法。当这三行的阴影格取定后，后三行和后三列的公共部分 $9$ 个格中，恰有 $3$ 个彼此不同行同列的格子无阴影，剩下的六个格子有阴影。显然选取这 $3$ 个无阴影的格子有 $3!=6$ 种方法，故此时有 $6\times 6=36$ 种涂阴影的方法。
综上所述，在第一列的阴影格给定的条件下，共有 $3+54=36=93$ 种涂阴影的方法，因此一共有 $20\times 93=1860$ 种涂阴影的方法，故所求的余数为 $860$ 。
若上方三行剩余的一个阴影格的所在列完全相同，则这个列有 $C_{3}^{1}=3$ 种选择方式，而这个列选好后，下方三行的阴影格也只有唯一的选取方式，此时有 $3$ 种涂阴影的方法。
若上方三行剩余的一个阴影格中，有两个所在的列相同，另一个所在的列不同，则先选取有两个阴影格的列，有 $C_{3}^{1}=3$ 种选择方式，再选取一个阴影格的列，有 $C_{2}^{1}=2$ 种选择方式，最后选取单独的阴影格所在行，有 $C_{3}^{1}=3$ 种选择方式，故这样的前三行有 $3\times 3\times 2=18$ 种涂阴影的方法。当前三行确定后，还有一列没有阴影格，故这一列的后 $3$ 个格子必须都是涂阴影的，另外的两列中，有一列差 $1$ 个阴影格，另一列差 $2$ 个阴影格，这三个阴影格必须在这两列与三行的公共部分中选出，易知这样的选法有 $C_{3}^{1}=3$ 种，因此此时有 $18\times 3=54$ 种涂阴影的方法。
若上方三行剩余的阴影格所在的列都不同，则选定它们所在的列（此即选定它们的位置）有 $3!=6$ 种涂阴影的方法。当这三行的阴影格取定后，后三行和后三列的公共部分 $9$ 个格中，恰有 $3$ 个彼此不同行同列的格子无阴影，剩下的六个格子有阴影。显然选取这 $3$ 个无阴影的格子有 $3!=6$ 种方法，故此时有 $6\times 6=36$ 种涂阴影的方法。
综上所述，在第一列的阴影格给定的条件下，共有 $3+54=36=93$ 种涂阴影的方法，因此一共有 $20\times 93=1860$ 种涂阴影的方法，故所求的余数为 $860$ 。
答案
解析
备注
