题目描述
对于一个 01 串（即由字符 0 和 1 组成的字符串）$s$，我们称 $s$ 合法，当且仅当串 $s$ 的任意一个长度为 $m$ 的子串 $s'$，不为全 1 串。
请求出所有长度为 $n$ 的 01 串中，有多少合法的串，答案对 $65537$ 取模。
输入格式
输入共一行，包含两个正整数 $n,m$。
输出格式
输出共一行，表示所求的和对 $65537$ 取模的结果。
样例 1
input
5 2output
13
以下是所有合法的串：
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101样例 2
input
2018 7output
27940
数据范围与提示
对于所有的数据，满足 $1\le n,m\le 68721573904$。
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
| Subtask # | 分值 | $n$ | $m$ |
|---|---|---|---|
| 1 | $6$ | $\le 18$ | $\le 18$ |
| 2 | $7$ | $\le 10^9$ | $\le 2$ |
| 3 | $15$ | $\le 10^6$ | $\le 10^6$ |
| 4 | $10$ | $\le 10^9$ | $\le 50$ |
| 5 | $14$ | $\le 10^9$ | $\le 500$ |
| 6 | $15$ | $\le 4295098369$ | - |
| 7 | $18$ | $\le 17180393476$ | - |
| 8 | $15$ | - | - |