#547. 「LibreOJ β Round #7」匹配字符串

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: spj

题目描述

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

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

输入格式

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

输出格式

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

样例

样例输入 1

5 2

样例输出 1

13

样例解释 1

以下是所有合法的串:

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

样例输入 2

2018 7

样例输出 2

27940

数据范围与提示

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

详细的数据限制及约定如下(留空表示和上述所有数据的约定相同):

Subtask # 分值 n m
1 6 \le 18
2 7 \le 10^9 \le 2
3 15 \le 10^6
4 10 \le 10^9 \le 50
5 14 \le 500
6 15 \le 4295098369 -
7 18 \le 17180393476
8 15 -