/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
問題文
N \times M のグリッドがあります。
このグリッドの各マスを白または黒で塗る 2^{NM} 通りについての、黒マスからなる連結成分の個数の和を求めてください。
より正確には以下の通りです：
グリッドの上から i 行目・左から j 列目のマスをマス (i,j) と表します。
2 つのマス (x,y) と (x',y') は |x-x'|+|y-y'|=1 を満たすとき、かつ、そのときに限り隣り合っているとみなします。
グリッドにおいて黒く塗られたマスを頂点集合、隣り合った 2 つの黒く塗られたマスを結ぶ辺全体を辺集合としたグラフにおける連結成分の個数を黒マスからなる連結成分の個数とします。
このグリッドの各マスを白または黒で塗る 2^{NM} 通りについての、黒マスからなる連結成分の個数の和を求めてください。
制約
- 1 \leq N,M \leq 7
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
2 2
出力例 1
17
マスの塗り方は以下の 16 通りあります。
黒マスの連結成分が 0 個となる塗り方が 1 通り、1 個となる塗り方が 13 通り、2 個となる塗り方が 2 通りあり、合計は 17 となります。
入力例 2
1 3
出力例 2
8
マスの塗り方は以下の 8 通りあります。
黒マスの連結成分が 0 個となる塗り方が 1 通り、1 個となる塗り方が 6 通り、2 個となる塗り方が 1 通りあり、合計は 8 となります。
入力例 3
7 6
出力例 3
22772408537381
Problem Statement
There is an N \times M grid.
For each of the 2^{NM} ways to paint each cell of the grid black or white, count the number of connected components formed by black cells, and find their sum.
More precisely, solve the following problem:
Let (i,j) denote the cell in row i and column j of a grid.
Two cells (x,y) and (x',y') are considered adjacent to each other if and only if |x-x'|+|y-y'|=1.
The number of connected components formed by black cells is defined as the number of connected components in the graph, whose vertex set is formed by the black cells in the grid, and edge set is formed by the pairs of black cells adjacent to each other.
For each of the 2^{NM} ways to paint each cell black or white, count the number of connected components formed by black cells, and find their sum.
Constraints
- 1 \leq N,M \leq 7
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
2 2
Sample Output 1
17
There are the following 16 ways of painting:
1 of them contains zero black connected components; 13 of them contain one connected component; 2 of them contain two black connected components, for a total of 17.
Sample Input 2
1 3
Sample Output 2
8
There are the following 8 ways of painting:
1 of them contains zero black connected components; 6 of them contain one connected component; 1 of them contains two black connected components, for a total of 8.
Sample Input 3
7 6
Sample Output 3
22772408537381