After the failure of “Bobo Encoding” (for information on “Bobo Encoding”, you may refer to the statement of “Binary String Construction”, but it is not necessary to understand this problem), Bobo decided to study strings carefully. Now he is considering a very simple problem:

Given a string  consisting of only s and s,  a positive integer , and an integer , you need to calculate the number of strings  consisting of only s and s with length exactly , satisfying:

•  The string  appears exactly  times in the string  (note that the appearance here can be overlapped, such as  appearing twice in ).

Since the answer may be too large, you need to output the answer modulo .

The first line contains two integers  (). 

The second line contains a binary string  ().

Output an integer in one line, denoting the answer modulo .

5 2
11

6

10 5
0

252

10 0
1001

631