##### Canadian Computing Olympiad: 2023 Day 1, Problem 1

You have been hired by the Cheap Communication Organization (CCO) to work on a communication breakthrough: sub-message sum (SMS). This revolutionary idea works as follows.

Given a binary string of length , and some positive integer with , the SMS for the string consists of a sequence of sums. The first sum in the sequence is the sum of digits through , the second sum is the sum of digits through , and so on until the last sum which is the sum of digits through .

For example, if , the SMS of the binary string `110010`

is . This is because
and .

Since you are a very junior developer, your job is not to find the original binary string from a given SMS, but rather the number of binary strings that could have formed this SMS.

#### Input Specification

The first line of input contains the two space-separated integers and where . The second line of input contains space-separated integers which is the SMS of at least one binary string.

Marks Awarded | Bounds on | Additional Bounds on |
---|---|---|

marks | ||

marks | None | |

marks | ||

marks | ||

marks | ||

marks | None |

#### Output Specification

Output the remainder of divided by the prime number where is the positive integer equal to the total number of possible binary strings that correspond to the given SMS.

#### Sample Input

```
7 4
3 2 2 2
```

#### Output for Sample Input

`3`

#### Explanation of Output for Sample Input

The possible strings of length are `1011001`

, `1101010`

, and `1110011`

.

## Comments