F. マスの塗り分け (むずかしい・パターン数:$30$)

問題文

この問題は、問題文の内容がC問題とほぼ同じです。赤字で示された部分がC問題と異なり、C問題にない文章は青字で示されています。

縦に $i$ マス、横に $j$ マスにわたる、合計 $ij$ 個の合同な正方形があります。これを、隣接するマスの色が異なる色になるように、ちょうど $4$ 色で塗り分けます。ただし、$1$ つのマスを塗るのに使える色は高々 $1$ 色となります。このときの塗り分け方を $A_{i,j}$ 通りとします。$\color{red}{i=2,3,4,5,6,7}$ について、$j=2,3,4,5,6$ における $A_{i,j}$ の値をそれぞれ求めてください。
$\color{blue}{この問題は桁が著しく大きくなるため、A_{i,j}を\ 10001\ で}$
$\color{blue}{割った余りを記述してください。}$

解答形式

$6$ 行にわたって入力してください。
空白区切り・半角で、以下の形で、$10001$ で割った余り記述してください。
$A_{2,2}$ $A_{2,3}$ $A_{2,4}$ $A_{2,5}$ $A_{2,6}$
$A_{3,2}$ $A_{3,3}$ $A_{3,4}$ $A_{3,5}$ $A_{3,6}$
$\cdots$
$A_{7,2}$ $A_{7,3}$ $A_{7,4}$ $A_{7,5}$ $A_{7,6}$