#547. 「LibreOJ β Round #7」匹配字符串
题目描述
对于一个 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 687215739041≤n,m≤68721573904。
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
| Subtask # | 分值 | nnn | mmm |
|---|---|---|---|
| 1 | 666 | ≤18\le 18≤18 | ≤18\le 18≤18 |
| 2 | 777 | ≤109\le 10^9≤109 | ≤2\le 2≤2 |
| 3 | 151515 | ≤106\le 10^6≤106 | ≤106\le 10^6≤106 |
| 4 | 101010 | ≤109\le 10^9≤109 | ≤50\le 50≤50 |
| 5 | 141414 | ≤109\le 10^9≤109 | ≤500\le 500≤500 |
| 6 | 151515 | ≤4295098369\le 4295098369≤4295098369 | - |
| 7 | 181818 | ≤17180393476\le 17180393476≤17180393476 | - |
| 8 | 151515 | - | - |