← 返回题目列表

Codeforces · 213/B

B. 数字

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

Furik 喜欢写各种问题,尤其是那些他自己无法解决的问题。你遇到了他的问题之一,福里克给卢比克带来的问题。魔方要求你解决它。

有整数 n 和数组 a,由 10 个整数组成,索引为 0 到 9 的数字。您的任务是计算具有以下属性的正整数的数量:

- 数字的长度不超过n;
- 该数字没有前导零;
- 数字 i (0 ≤ i ≤ 9) 至少出现 a[i] 次。

输入

第一行包含整数 n (1 ≤ n ≤ 100)。下一行包含 10 个整数 a[0]、a[1]、...、a[9] (0 ≤ a[i] ≤ 100) — 数组 a 的元素。数字之间用空格分隔。

输出

在一行中打印问题答案除以 1000000007 (109 + 7) 的余数。

示例

输入 #1

1
0 0 0 0 0 0 0 0 0 1

输出 #1

1

输入 #2

2
1 1 0 0 0 0 0 0 0 0

输出 #2

1

输入 #3

3
1 1 0 0 0 0 0 0 0 0

输出 #3

36

注意

第一个样品中编号 9 符合要求。

第二个样品中编号10符合要求。

第三个样品编号10、110、210、120、103符合要求。还有其他合适的数字,总共36个。