2854. 统计特定字串模式的个数

Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

在 0 和 1 组成的长度为 n (1≤n≤31)的字符串中,统计包含 m (1≤m≤n)个连续 1 子串的字符串的个数。

Input

本题有多组测试数据。每组测试数据占一行,含 n 和 m,表示字符串的长度和连续 1 的个数。n=-1 和 m=-1 表示输入结束。

Output

对每组测试数据,在一行中输出统计出的字符串的个数。

Examples

Input
1 1
2 1
3 1
4 3
10 3
10 5
20 10
20 15
31 20
31 1
-1 -1
Output
1
3
7
3
520
112
6144
112
13312
2147483647
Notes
长度为4,包含3个连续1子串的字符串有3个:
0111,1110,1111

274 Solved out of 336 users tried.

384 Accepted out of 650 tried.

1.8 EMB will be rewarded for solving this problem.

Created: 7 years, 7 months ago.

Updated: 1 week, 6 days ago.

Latest Submission: 5 days, 3 hours ago.

Source: 编程实践第3次考试

Problem Tags
DP