题目描述

有一个 $n×m$ 的网格，现在我们想用 $1×2$ 的矩形铺满它，要求矩形只能横着铺或者竖着铺、矩形不能超出网格的边界并且不同的矩形之间不能相互覆盖。

请问有多少种不同的铺法，输出对 $10^9+7$ 取模的结果。

输入格式

一行两个整数 $n,m$ 表示网格的大小。

输出格式

一行一个整数表示答案。

Samples

2 3

3

16 5

366944287

3 3

0

数据范围

对于 $100\%$ 的数据，$1≤n≤10^9,2≤m≤7$。