## CCO '23 P1 - Binaria

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 1G

Author:
Problem types

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 AwardedBounds 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.