斗地主

题号：NC229891
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛一个人在打牌（他失去了牛妹），他有 $m$ 种类型的牌，每种牌的分值是 $a_1,a_2\dots a_m$ 。

第 $0$ 回合时牛牛的分值为 $0$ 。每回合他都会打出一张牌，然后新的分值就是上一回合得分值加上这张牌的分值再对 $k$ 取模。

牛牛喜欢一个数字，当且仅当数字中含有 $7$ 或者含有 $9$ 。请你告诉他 $n$ 轮后他分值会是他所"喜欢"的方案数。

我们认为两种方案不同，当且仅当存在某一个回合牛牛打出的牌不同。

由于答案可能非常大，你只需要输出其对于 $10^9+7$ 取模的结果。

输入描述:

第一行包含三个数 。

第二行  个数，第  个数表示 。

，，。

输出描述:

仅有一个数，牛牛打出”喜欢“数字的分值的方案数。

示例1

输入

复制

5 2 8
1 6

输出

复制