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
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.
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|
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.
7 4 3 2 2 2
Output for Sample Input
Explanation of Output for Sample Input
The possible strings of length are