UVA13284 Macarons

Description

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=878&page=show_problem&problem=5208 [PDF](https://uva.onlinejudge.org/external/132/p13284.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA13284/257bc3f55fb5485142b6468a7e54ffe6077eb52a.png)

Input Format

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA13284/f994cb5ace1d1fe31afbace4ebd6a66ec449b97f.png)

Output Format

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA13284/fe9f91d92950d7ae818e4535c70bcfaeb65571e6.png)

Explanation/Hint

## 翻译 **题目描述** 用 $1 \times 1$ 或 $1 \times 2$ 的矩形铺满长为 $N$ ，宽为 $M$ 的桌子，满足 $N < M$ ，并求出有多少种铺满的方案。 **输入格式** 输入 $N (1 \leq N \leq 8)$，$M (1 \leq M \leq 10^{18})$ 。注意有多组数据！ **输出格式** 对于每组数据，输出方案数模 $10^9$ 后的值。