题目描述

对于一个 $01$ 串（即由字符 $0$ 和 $1$ 组成的字符串）$s$，我们称 $s$ 合法，当且仅当串 $s$ 的任意一个长度为 $m$ 的子串 $s'$，不为全 $1$ 串。

请求出所有长度为 $n$ 的 $01$ 串中，有多少合法的串，答案对 $65537$ 取模。

输入格式

输入共一行，包含两个正整数 $n,m$。

输出格式

输出共一行，表示所求的和对 $65537$ 取模的结果。

5 2

13

2018 7

27940

提示

样例 1 解释

以下是所有合法的串：

00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101

数据范围

对于所有的数据，满足 $1\le n,m\le 68721573904$。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：