Problem

Source: Switzerland - 2015 Swiss MO Final Round p6

Tags: combinatorics, combinatorial geometry



We have an $8\times 8$ board. An interior edge is an edge between two $1 \times 1$ cells. we cut the board into $1 \times 2$ dominoes. For an inner edge $k$, $N(k)$ denotes the number of ways to cut the board so that it cuts along edge $k$. Calculate the last digit of the sum we get if we add all $N(k)$, where $k$ is an inner edge.