3686: 序列(第二轮04)

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：0

题目描述

定义一个数的 se 序列为其一个数位和为 10 的子段。

举个例子， 1145141919810900 的所有 se 序列为

      •     145

•    451

•     514

•     19

•     91

•     19

•     109

•     1090

•     10900

定义一个数是 ll 数，当且仅当它的每一个数位都在至少一个 se 序列中。

举个例子，1145141919810900 不是 ll 数，因为第一个 1 和 8 不在任何一个 se 序 列中，而 23541901 是一个 ll 数。

现在牛牛想随机生成一个 [0,10n)范围内的数送给牛妹。具体地说，每一位上的

数字为 i的概率为ai   ，且保证 ∑i(9)=0 ai   =  1 现在牛牛想知道这个数为 ll 数的概率。

输入

一行 11 个数， 表示n, b0, b1, b2, b3, b4, b5, b6, b7, b8, b9 。

输出

输出随机数为 ll 数的概率，答案对 109 + 7取模。

样例输入 复制 

5 1 1 1 1 1 1 1 1 1 1

样例输出 复制 

566440004

提示

【样例 1 输入】

5 1 1 1 1 1 1 1 1 1 1

【样例 1 输出】

566440004

【样例 2 输入】

100000 1234 2341 681 2341 1 31 321 1324 1 15

【样例 2 输出】

14603672

【数据范围】

对于 5% 的数据， n =  1；

对于 5% 的数据， n  = 100；

对于 20% 的数据， n = 3000；

对于另 30% 的数据， n ≤ 10^18，

对于 100% 的数据， 1 ≤ n ≤ 1018 。

来源/分类

提交提交记录统计露一手!