题目描述

你参加了一档游戏节目，并进入了最终轮。现在有若干张卡片，第 $i$ 张卡片上写着一个十进制数字串 cards[i]。数字串可以包含前导零。

你面前有一块由若干行组成的面板。第 $i$ 行有 blank[i] 个连续空位。游戏按如下方式进行：

1. 按照输入中卡片的顺序依次打出卡片；
2. 每次打出一张卡片时，从当前所有仍为空的空位中等概率随机选择一个，将该卡片放入该位置；
3. 一旦某一整行被填满，游戏立即结束。

游戏结束后，将刚刚填满的那一行从左到右拼接起来，得到一个十进制整数，这个整数就是你的奖金。前导零不会影响该整数的数值。

设奖金的期望值化为最简分数 $P/Q$。令 $M=10^9+7$。可以证明 $Q$ 与 $M$ 互质。请输出

$P\cdot Q^{-1}\bmod M$，

其中 $Q^{-1}$ 表示 $Q$ 在模 $M$ 意义下的乘法逆元。

输入格式

第一行输入一个整数 $n$，表示卡片数量。

接下来 $n$ 行，每行输入一个数字串，依次表示各张卡片上的内容。

随后一行输入一个整数 $m$，表示面板的行数。

最后一行输入 $m$ 个整数 $b_1,b_2,\ldots,b_m$，其中 $b_i$ 表示第 $i$ 行的空位数量。

输出格式

输出一个整数，表示奖金期望值在模 $10^9+7$ 意义下的结果。

数据范围

• $1\le n\le 50$；
• 每张卡片长度为 $1\sim 50$，只包含字符 0 到 9；
• $1\le m\le n$；
• $1\le b_i\le n$；
• $\sum b_i\le n+m-1$。

样例

输入

4
123
45
6
7
1
3

输出

401988

说明

唯一一行有三个位置，因此前三张卡片会以随机顺序占据这三个位置。六种奖金分别为 123456、123645、451236、456123、612345、645123，其平均值为 $401988$。