#67. 【82课】【3456】选数

【82课】【3456】选数

说明

已知 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>�</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>�</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mtext> </mtext><mo separator="true">,</mo><msub><mi>�</mi><mi>�</mi></msub></mrow></semantics></math>x1,x2,,xn,以及 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow></semantics></math>1 个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>k<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo><</mo><mi>�</mi></mrow></semantics></math>k<n)。从 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个整数中任选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>k 个整数相加,可分别得到一系列的和。例如当 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo>=</mo><mn>4</mn></mrow></semantics></math>n=4<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo>=</mo><mn>3</mn></mrow></semantics></math>k=3<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>4</mn></mrow></semantics></math>4 个整数分别为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo separator="true">,</mo><mn>7</mn><mo separator="true">,</mo><mn>12</mn><mo separator="true">,</mo><mn>19</mn></mrow></semantics></math>3,7,12,19 时,可得全部的组合与它们的和为:

<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>+</mo><mn>7</mn><mo>+</mo><mn>12</mn><mo>=</mo><mn>22</mn></mrow></semantics></math>3+7+12=22

<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>+</mo><mn>7</mn><mo>+</mo><mn>19</mn><mo>=</mo><mn>29</mn></mrow></semantics></math>3+7+19=29

<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>7</mn><mo>+</mo><mn>12</mn><mo>+</mo><mn>19</mn><mo>=</mo><mn>38</mn></mrow></semantics></math>7+12+19=38

<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>+</mo><mn>12</mn><mo>+</mo><mn>19</mn><mo>=</mo><mn>34</mn></mrow></semantics></math>3+12+19=34

现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>+</mo><mn>7</mn><mo>+</mo><mn>19</mn><mo>=</mo><mn>29</mn></mrow></semantics></math>3+7+19=29


输入格式

第一行两个空格隔开的整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo separator="true">,</mo><mi>�</mi></mrow></semantics></math>n,k<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>�</mi><mo>≤</mo><mn>20</mn></mrow></semantics></math>1n20<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo><</mo><mi>�</mi></mrow></semantics></math>k<n)。

第二行 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个整数,分别为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>�</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>�</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mtext> </mtext><mo separator="true">,</mo><msub><mi>�</mi><mi>�</mi></msub></mrow></semantics></math>x1,x2,,xn<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo><msub><mi>�</mi><mi>�</mi></msub><mo>≤</mo><mn>5</mn><mo>×</mo><mn>1</mn><msup><mn>0</mn><mn>6</mn></msup></mrow></semantics></math>1xi5×106

输出格式

对于每组输入数据,输出一个整数,表示满足条件的种数。

样例

4 3
3 7 12 19
1

提示

NOIP 2002 普及组第二题