Description

派大星喜欢含有 7 的数字。

派大星过目不忘。

派大星真是太强了。

派大星看到一串长度至少是 $1$ 的数字。

派大星发现这串数字 **不含前导 $0$ ** 且 不是 $7$ 的数字不超过 $3000$ 个 。

派大星一个个数字看了过去。

派大星的大脑每看到一个数字就会记住它至少一次。

派大星的大脑现在有了一堆数字。

派大星发现不记得这些数字谁先来谁后来了。

派大星倒下了。

派大星求助的看向了你。

派大星告诉你她大脑里共有数字 $N$。

派大星按照某个随机顺序把它大脑的的数字一个个告诉了你，告诉你的第 $i$ 个数字是 $A_i$。

派大星想知道他一开始看到的数字串有多少可能性（对 $1, 000, 000, 007$ 取模）。

举个例子：假设派大星看到 $2008$

• 派大星脑中可能是 $222000888$、$00088882$、$2008$、$8020$ 等等。

• 但不可能是 $2081$、$208$、$1567$ 等等

Input Format

从文件 lucky.in 读入数据

第一行给定一个整数 $N（1 \le N \le 500000）$，代表派大星脑中的数字数量。

接下来 $N$ 个数字，每个数字为 $0$ ~ $9$，第 $i$ 个数字为 $A_i$。

保证除了 $7$ 以外的数字个数不超过 $3000$ 个，且至少存在一个非 $0$ 的数字。

Output Format

向文件lucky.out 输出数据

输出一个整数（对 $1,000,000,007$ 取模）代表派大星看到的数字串有多少可能性。

再次强调派大星看到的数字不含前导 $0$ 。

Sample

样例输入1

4
7 7 7 7

样例输出1

4

样例1解释

所有可能答案为 $7$, $77$, $777$, $7777$。

样例输入2

4
7 0 7 8

样例输出2

13

Hint

| part | $n$ |

| ------ | -------------------- |

| $20\%$ | $1 \le n \le 18$ |

| $50\%$ | $1 \le n \le 5000$ |

| $all$ | $1 \le n \le 500000$ |