题目描述

给定一块 $N\times M$ 的棋盘，每个格子最多只能放一颗棋子（称之为车），也可以不放。请问，若要使得每一行每一列都至少存在一颗棋子，有几种放置棋子的方案数？

由于答案很大，请输出总方案数量取模 $1,000,000,007$ 的余数。

输入格式

• 两个整数表示 $N$ 与 $M$

输出格式

• 单个整数表示答案。

3 5

16081

86 68

654239212

2 2

7

样例解释 3

ox xo oo ox oo xo oo
xo ox ox oo xo oo oo

数据范围

• $30\%$ 的数据，$1\leq N,M\leq 10$
• $60\%$ 的数据，$1\leq N,M\leq 10^4$
• $100\%$ 的数据，$1\leq N,M\leq 10^6$