Peter and Array

View as PDF

Points: 5 (partial)
Time limit: 5.0s
Memory limit: 64M

Author:
Problem types

Peter has dropped his precious array into a pile of arrays. Jumbled up with the rest of the arrays, Peter can't figure out which array is his. Peter remembers some elements of his array, and that all the numbers in his array are positive integers less than or equal to . Peter also remembers that his array is beautiful.

According to Peter, an array is beautiful if it has multiple 3-splits with the same value. A 3-split is a partition of an array into 3 non-empty sections. The value of a 3-split is the product of the sums of the three sections. Two 3-splits are different if one element is in a different section in each split.

Formally, Peter thinks an array is beautiful if there exist multiple distinct partitions of the array into 3 non-empty segments such that the product of the sums of the segments is the same.

Peter wants to know how many possibilities there are for what his array was, to gauge his chances of finding it.

Input Specification

The first line will contain two integers , the length of Peter's array, and .

The next line contains integers, the values of Peter's array, or ? if Peter has forgot the value of that element.

Let the amount of ?s be .

Output Specification

On one line, print the number of possible arrays that Peter could've had.

Sample Input

5 5
2 ? 5 3 4

Sample Output

2

Explanation of Sample

When the ? is replaced with 1, you can the 3-splits 2 1|5 3|4, and 2 1 5|3|4 both have a value of 96. When the ? is replaced with 4, the 3-splits 2|4|5 3 4, and 2|4 5 3|4 both also have a value of 96. All other values of ? result of arrays that aren't beautiful, thus the answer is 2.