题目描述

给定一个 N × M 的网格。你需要把每个格子染成红色或蓝色。

要求：对于任意一个格子，它必须在 同一行或同一列 中至少还能找到一个与自己颜色相同的格子。
注意是“同一行 或 同一列”即可，不要求两者都满足。

换句话说，任意格子都不能“孤单”。例如：

• 一整行全部染成红色是允许的；
• 一个格子在本行内没有同色格子，但在本列内有同色格子，也仍然合法。

题目不要求两种颜色都必须出现，因此整张纸全部染成蓝色也是合法方案。

请你计算合法染色方案总数。两个方案不同，当且仅当存在至少一个格子在一个方案中是红色，而在另一个方案中是蓝色。

输入格式

输入一行两个整数 N, M，表示网格的行数和列数。

输出格式

输出一个整数，表示合法染色方案数对 1 000 000 007 取模后的结果。

数据范围

• 1 <= N, M <= 50

子任务与评分

• 30% 的测试满足：1 <= N, M <= 5
• 60% 的测试满足：min(N, M) <= 7

样例 #1

输入 #1

3 3

输出 #1

284

样例 #2

输入 #2

5 4

输出 #2

898416

样例 #3

输入 #3

13 17

输出 #3

390317257

样例 #4

输入 #4

42 42

输出 #4

193467102