#P1622D. Shuffle
-
ID: 6244
Type: RemoteJudge
2000ms
512MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Shuffle
No submission language available for this problem.
Description
You are given a binary string (i. e. a string consisting of characters 0 and/or 1) of length . You can perform the following operation with the string at most once: choose a substring (a contiguous subsequence) of having exactly characters 1 in it, and shuffle it (reorder the characters in the substring as you wish).
Calculate the number of different strings which can be obtained from by performing this operation at most once.
The first line contains two integers and (; ).
The second line contains the string of length , consisting of characters 0 and/or 1.
Print one integer — the number of different strings which can be obtained from by performing the described operation at most once. Since the answer can be large, output it modulo .
Input
The first line contains two integers and (; ).
The second line contains the string of length , consisting of characters 0 and/or 1.
Output
Print one integer — the number of different strings which can be obtained from by performing the described operation at most once. Since the answer can be large, output it modulo .
Samples
Note
Some strings you can obtain in the first example:
- to obtain 0110110, you can take the substring from the -st character to the -th character, which is 1100, and reorder its characters to get 0110;
- to obtain 1111000, you can take the substring from the -rd character to the -th character, which is 00110, and reorder its characters to get 11000;
- to obtain 1100101, you can take the substring from the -th character to the -th character, which is 110, and reorder its characters to get 101.
In the second example, so you can only choose the substrings consisting only of 0 characters. Reordering them doesn't change the string at all, so the only string you can obtain is 10010.