Nastya and a Game

2000ms

262144K

Description:

Nastya received one more array on her birthday, this array can be used to play a traditional Byteland game on it. However, to play the game the players should first select such a subsegment of the array that $\text{[math]}$ , where p is the product of all integers on the given array, s is their sum, and k is a given constant for all subsegments.

Nastya wonders how many subsegments of the array fit the described conditions. A subsegment of an array is several consecutive integers of the array.

Input:

The first line contains two integers n and k (1 ≤ n ≤ 2·10⁵, 1 ≤ k ≤ 10⁵), where n is the length of the array and k is the constant described above.

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁸) — the elements of the array.

Output:

In the only line print the number of subsegments such that the ratio between the product and the sum on them is equal to k.

Sample Input:

1 1
1

Sample Output:

Sample Input:

4 2
6 3 8 1

Sample Output:

Note:

In the first example the only subsegment is [1]. The sum equals 1, the product equals 1, so it suits us because $\text{[math]}$ .

There are two suitable subsegments in the second example — [6, 3] and [3, 8, 1]. Subsegment [6, 3] has sum 9 and product 18, so it suits us because $\text{[math]}$ . Subsegment [3, 8, 1] has sum 12 and product 24, so it suits us because $\text{[math]}$ .

Informação

Provedor Codeforces

Código CF992D