[Ahoi2009]chess 中国象棋

在 $N$ 行 $M$ 列的棋盘上放若干个炮（可以是 $0$ 个），使得没有任何一个炮可以攻击到另一个炮。

请问有多少种放置方法。中国象棋中炮的行走方式大家应该很清楚：炮在同一行或同一列上，隔着恰好一个棋子可以攻击到对方。

输入格式

一行包含两个整数 $N, M$，中间用空格分开。

输出格式

输出所有的方案数。由于值比较大，输出其对 $9999973$ 取模的结果。

样例输入

1 3

样例输出

7

样例解释

$1$ 行 $3$ 列的棋盘上，除了在 $3$ 个格子中都放满炮的情况（此时中间的炮会被两侧的炮攻击）外，其它的放法都可以，共 $2^3-1=7$ 种。

数据范围

• 对于 $100\%$ 的数据，$N, M$ 不超过 $100$；
• 对于 $50\%$ 的数据，$N, M$ 至少有一个数不超过 $8$；
• 对于 $30\%$ 的数据，$N, M$ 均不超过 $6$。

来源与许可

本题为 AHOI 2009 试题「chess 中国象棋」，题面与测试数据整理自 BZOJ 1801。

样例 1

输入

1 3

输出

7