莫莉·胡珀 (Molly Hooper) 有 n 种不同种类的化学品排列成一行。每种化学物质都有一个情感值,其中第 i 个具有情感值 ai。
莫莉希望夏洛克爱上她。为此,她打算将一段连续的化学物质混合在一起,制成一种爱情药水,其总感情值为 k 的非负整数次方。化学品连续段的总影响值是该段中每种化学品影响值的总和。
帮助她找到此类片段的总数。
输入
输入的第一行包含两个整数,n和k,化学品的数量和数量,使得总影响值是该数量k的非负幂。 (1 ≤ n ≤ 105,1 ≤ |k| ≤ 10)。
下一行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) – 化学品的影响值。
输出
输出一个整数——有效段的数量。
示例
输入 #1
4 2 2 2 2 2
输出 #1
8
输入 #2
4 -3 3 -6 -3 12
输出 #2
3
注意
请记住 k0 = 1。
在第一个示例中,Molly 可以获得以下不同的情感值:
- 2:段[1, 1]、[2, 2]、[3, 3]、[4, 4];
- 4:段[1, 2]、[2, 3]、[3, 4];
- 6:段[1, 3],[2, 4];
- 8:段 [1, 4]。
其中,2、4 和 8 是 k = 2 的幂。因此,答案是 8。
在第二个示例中,Molly 可以选择段 [1, 2]、[3, 3]、[3, 4]。