P1817 Grid Coloring

Given an $N \times M$ grid, each cell can be colored black or white. All black cells must be connected, all white cells must be connected, and at least one black cell is on the border while at least one white cell is on the border. How many valid colorings are there?

The first line contains two positive integers $N, M$.

Output a single positive integer representing the answer.

Constraints: For $100 \%$ of the testdata: $1 \le N \le 7$, $1 \le M \le 8$. Translated by ChatGPT 5