#F0140. #547. 「LibreOJ β Round #7」匹配字符串
#547. 「LibreOJ β Round #7」匹配字符串
题目描述
对于一个 01 串（即由字符 0 和 1 组成的字符串），我们称 合法，当且仅当串 的任意一个长度为 的子串 ，不为全 1 串。
请求出所有长度为 的 01 串中，有多少合法的串，答案对 取模。
输入格式
输入共一行，包含两个正整数 。
输出格式
输出共一行，表示所求的和对 取模的结果。
样例
样例输入 1
5 2样例输出 1
13样例解释 1
以下是所有合法的串：
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101样例输入 2
2018 7样例输出 2
27940数据范围与提示
对于所有的数据，满足 。
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
| Subtask # | 分值 | ||
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 | - | ||
| 7 | - | ||
| 8 | - | - |
题目来源：fps-loj-small-pics.zip；FPS 共享题包，题包内第 22 题。保留原作者与原赛事署名。