{"raw_statement":[{"iden":"statement","content":"Molly Hooper has _n_ different kinds of chemicals arranged in a line. Each of the chemicals has an affection value, The _i_\\-th of them has affection value _a__i_.\n\nMolly wants Sherlock to fall in love with her. She intends to do this by mixing a contiguous segment of chemicals together to make a love potion with total affection value as a non-negative **integer** power of _k_. Total affection value of a continuous segment of chemicals is the sum of affection values of each chemical in that segment.\n\nHelp her to do so in finding the total number of such segments."},{"iden":"input","content":"The first line of input contains two integers, _n_ and _k_, the number of chemicals and the number, such that the total affection value is a non-negative power of this number _k_. (1 ≤ _n_ ≤ 105, 1 ≤ |_k_| ≤ 10).\n\nNext line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109) — affection values of chemicals."},{"iden":"output","content":"Output a single integer — the number of valid segments."},{"iden":"examples","content":"Input\n\n4 2\n2 2 2 2\n\nOutput\n\n8\n\nInput\n\n4 -3\n3 -6 -3 12\n\nOutput\n\n3"},{"iden":"note","content":"Do keep in mind that _k_0 = 1.\n\nIn the first sample, Molly can get following different affection values:\n\n*   2: segments \\[1, 1\\], \\[2, 2\\], \\[3, 3\\], \\[4, 4\\];\n    \n*   4: segments \\[1, 2\\], \\[2, 3\\], \\[3, 4\\];\n    \n*   6: segments \\[1, 3\\], \\[2, 4\\];\n    \n*   8: segments \\[1, 4\\].\n\nOut of these, 2, 4 and 8 are powers of _k_ = 2. Therefore, the answer is 8.\n\nIn the second sample, Molly can choose segments \\[1, 2\\], \\[3, 3\\], \\[3, 4\\]."}],"translated_statement":[{"iden":"statement","content":"Molly Hooper 有 #cf_span[n] 种不同的化学试剂排成一行。每种化学试剂都有一个情感值，第 #cf_span[i] 种化学试剂的情感值为 #cf_span[ai]。\n\nMolly 希望 Sherlock 爱上她。她打算通过混合一段连续的化学试剂来制作一种魔药，使得总情感值为 #cf_span[k] 的非负整数次幂。一段连续化学试剂的总情感值等于该段中所有化学试剂情感值的和。\n\n请帮助她找出满足条件的连续段的总数。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]，分别表示化学试剂的数量以及总情感值必须是其非负整数次幂的数 #cf_span[k]。（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ |k| ≤ 10]）。\n\n接下来一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 109 ≤ ai ≤ 109]）—— 化学试剂的情感值。\n\n请输出一个整数——满足条件的连续段的数量。\n\n请注意，#cf_span[k0 = 1]。\n\n在第一个样例中，Molly 可以得到以下不同的总情感值：\n\n \n\n \n\n \n\n其中，#cf_span[2]、#cf_span[4] 和 #cf_span[8] 是 #cf_span[k = 2] 的幂，因此答案为 #cf_span[8]。\n\n在第二个样例中，Molly 可以选择段 #cf_span[[1, 2]]、#cf_span[[3, 3]]、#cf_span[[3, 4]]。"},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]，分别表示化学试剂的数量以及总情感值必须是其非负整数次幂的数 #cf_span[k]。（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ |k| ≤ 10]）。接下来一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 109 ≤ ai ≤ 109]）—— 化学试剂的情感值。"},{"iden":"output","content":"请输出一个整数——满足条件的连续段的数量。"},{"iden":"examples","content":"输入\n4 2\n2 2 2 2\n输出\n8\n\n输入\n4 -3\n3 -6 -3 12\n输出\n3"},{"iden":"note","content":"请注意，#cf_span[k0 = 1]。\n\n在第一个样例中，Molly 可以得到以下不同的总情感值：\n#cf_span[2]：段 #cf_span[[1, 1]]、#cf_span[[2, 2]]、#cf_span[[3, 3]]、#cf_span[[4, 4]]；\n#cf_span[4]：段 #cf_span[[1, 2]]、#cf_span[[2, 3]]、#cf_span[[3, 4]]；\n#cf_span[6]：段 #cf_span[[1, 3]]、#cf_span[[2, 4]]；\n#cf_span[8]：段 #cf_span[[1, 4]]。\n其中，#cf_span[2]、#cf_span[4] 和 #cf_span[8] 是 #cf_span[k = 2] 的幂，因此答案为 #cf_span[8]。\n\n在第二个样例中，Molly 可以选择段 #cf_span[[1, 2]]、#cf_span[[3, 3]]、#cf_span[[3, 4]]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of chemicals.  \nLet $ k \\in \\mathbb{Z} \\setminus \\{0\\} $, $ |k| \\leq 10 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in [-10^9, 10^9] $.  \n\nLet $ S(i,j) = \\sum_{\\ell=i}^{j} a_\\ell $ denote the sum of the contiguous segment from index $ i $ to $ j $, for $ 1 \\leq i \\leq j \\leq n $.  \n\nLet $ P = \\{ k^m \\mid m \\in \\mathbb{Z}_{\\geq 0} \\} $ be the set of non-negative integer powers of $ k $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq |k| \\leq 10 $  \n3. $ -10^9 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCount the number of pairs $ (i,j) $ with $ 1 \\leq i \\leq j \\leq n $ such that $ S(i,j) \\in P $.","simple_statement":null,"has_page_source":false}