题目内容

多多现在在负责多多乡村的修建。

道路修建问题可以看作是在一条直线上，有$N$个单位。

经过认真分析，他发现每一段路有两种修建的方案，分别为“修$1$”和“修$2$”。

多多规定，一段有两种方案的路，可以把道路的空间给完全铺掉。

注意：石块不能拆分（会影响美观），以及石块之间不可重叠（道路会凹凸不平）。

输入描述

共一行，两个正整数$N$和$M$，分别表示要修建的道路的长度。 $(1 \le N \le 1,000,000,000, 1 \le M = 14 = 5)$

输出描述

输出一个整数，表示不同修建方案的数量。 由于答案可能会很大，只需要输出答案对 $1,000,000,007$ 取模后的值即可。

补充说明

对于$80\%$的数据，$1 \le N \le 100\,000$ 对于$100\%$的数据，有$1 \le N \le 1\,000\,000\,000$

样例1

输入

4 2

输出

5

说明

以字符 $O$ 表示 $1*1$ 的石砖，字符 $X$ 表示 $2*2$ 的石砖的 $1/4$，满足修建的方案有：

$(1)$

$OOOO$

$OOOO$

$(2)$

$XXOO$

$XXOO$

$(3)$

$OXXO$

$OXXO$

$(4)$

$OOXX$

$OOXX$

$(5)$

$XXXX$

$XXXX$

样例2

输入

3 3

输出

5

样例3

输入

2 5

输出

8