题目描述

用$1\times1$或$1\times2$的矩形铺满长为$N$，宽为$M$的桌子，满足$N < M$，并求出有多少种铺满的方案。

输入格式

输入$N(1 \leq N \leq 8)$，$M(1 \leq M \leq 10^{18})$。

注意有多组数据！

输出格式

对于每组数据，输出方案数模$10^9$后的值

输入样例

2

2

2

4

输出样例

7

71

---

源码如下

## 题目描述
用$1\times1$或$1\times2$的矩形铺满长为$N$，宽为$M$的桌子，满足$N < M$，并求出有多少种铺满的方案。
## 输入格式
输入$N(1 \leq N \leq 8)$，$M(1 \leq M \leq 10^{18})$。

注意有多组数据！
## 输出格式
对于每组数据，输出方案数模$10^9$后的值
## 输入样例
2

2

2

4
## 输出样例
7

71