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

Memory Limit:512 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

输入格式

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

输出格式

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

样例

样例输入 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≤n,m≤687215739041\le n,m\le 687215739041n,m68721573904

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

Subtask # 分值 nnn mmm
1 666 ≤18\le 1818 ≤18\le 1818
2 777 ≤109\le 10^9109 ≤2\le 22
3 151515 ≤106\le 10^6106 ≤106\le 10^6106
4 101010 ≤109\le 10^9109 ≤50\le 5050
5 141414 ≤109\le 10^9109 ≤500\le 500500
6 151515 ≤4295098369\le 42950983694295098369 -
7 181818 ≤17180393476\le 1718039347617180393476 -
8 151515 - -