#P1817. Connected Grid Coloring

    ID: 15100 Type: Default 1000ms 256MiB

Connected Grid Coloring

Connected Grid Coloring

Given an \(N \times M\) grid, each cell can be colored black or white. The constraints are:

  • All black cells form a connected region, i.e. for any two black cells there is a path from one to the other moving only up, down, left, or right through black cells.
  • All white cells form a connected region (under the same connectivity definition).
  • At least one black cell must lie on the boundary of the grid.
  • At least one white cell must lie on the boundary of the grid.

Your task is to calculate the number of valid colorings of the grid that satisfy the above conditions.

Note: A configuration where all cells are of the same color is invalid. The grid cells are indexed from 0 such that a cell is on the boundary if it is in the first row, last row, first column, or last column.

inputFormat

The input consists of a single line containing two integers \(N\) and \(M\) (the number of rows and columns of the grid, respectively).

outputFormat

Output a single integer, representing the number of valid ways to color the grid.

sample

1 1
0