骨牌覆盖

题目描述

给定一个 $n \times m$ 的棋盘，你需要用 $1 \times 2$ 的多米诺骨牌去覆盖整个棋盘，请求出有多少种不同的覆盖方案。由于答案可能很大，请输出答案模 $10^9 + 7$。

输入格式

第一行两个整数 $n, m$。

输出格式

一行一个数表示答案模 $10^9 + 7$ 的结果。

样例输入

2 3

样例输出

3

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^9, 1\leq m \leq 5$。