← 返回题目列表

Codeforces · 145/C

C. 幸运子序列

中文机器翻译题面 查看原题

Petya非常喜欢幸运数字。大家都知道,幸运数字是正整数,其小数记录中仅包含幸运数字4和7。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。

Petya 具有由 n 个整数组成的序列 a。

序列a的子序列是可以从a中删除零个或多个元素而获得的子序列。

如果两个序列中包含的数字索引集不同,则认为两个序列不同。也就是说,元素的值在子序列的比较中并不重要。特别是,任何长度为 n 的序列都恰好有 2n 个不同的子序列(包括空子序列)。

如果子序列的长度恰好为 k 并且不包含两个相同的幸运数字(不幸的数字可以重复任意次),则该子序列被认为是幸运的。

帮助 Petya 找出序列 a 的不同幸运子序列的数量。由于 Petya 的父母不让他玩大数,因此您应该打印对素数 1000000007 (109 + 7) 取模的结果。

输入

第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 105)。下一行包含 n 个整数 ai (1 ≤ ai ≤ 109) — 序列 a。

输出

在单行上打印单个数字——以素数 1000000007 (109 + 7) 为模的问题的答案。

示例

输入 #1

3 2
10 10 10

输出 #1

3

输入 #2

4 2
4 4 7 7

输出 #2

4

注意

在第一个样本中,所需长度的所有 3 个子序列都被认为是幸运的。

在第二个样本中有 4 个幸运子序列。对于它们来说,索引集相等(索引从 1 开始):{1, 3}、{1, 4}、{2, 3} 和 {2, 4}。