CF776C Molly's Chemicals

Tohru从异世界带回来 n 种化学品，排列成一行。 每一种化学品有一个效果值, 第i个效果值为a _i_ 。 Tohru想要Kobayashi爱上她。 她把连续的区间上的化学品混合在一起做成总效果值为k的非负整数幂的媚药。总效果值为连续区间上的化学品效果值的总和。 帮帮她找到符合要求的区间的方案数。

第一行有两个整数n和k，表示化学品的总数，以及k的值. (1 ≤ n ≤ 10^5, 1 ≤ |k| ≤ 10). 下一行有n 整数a_1_, a_2_, ..., a_n_ ( - 10^9 ≤ ai ≤ 10^9)表示化学品的效果值。

输出一个整数，表示方案总数。

Do keep in mind that $ k^{0}=1 $ . In the first sample, Molly can get following different affection values: - $ 2 $ : segments $ [1,1] $ , $ [2,2] $ , $ [3,3] $ , $ [4,4] $ ; - $ 4 $ : segments $ [1,2] $ , $ [2,3] $ , $ [3,4] $ ; - $ 6 $ : segments $ [1,3] $ , $ [2,4] $ ; - $ 8 $ : segments $ [1,4] $ . Out of these, $ 2 $ , $ 4 $ and $ 8 $ are powers of $ k=2 $ . Therefore, the answer is $ 8 $ . In the second sample, Molly can choose segments $ [1,2] $ , $ [3,3] $ , $ [3,4] $ .