Фурику нравится придумывать разные задачи, особенно те, которые он сам решить не может. Перед вами очередная задача Фурика, которую он дал Рубику. Рубик же просит вас решить ее.
Имеется целое число n и массив a, состоящий из десяти целых чисел, проиндексированный номерами от 0 до 9. Нужно посчитать количество целых положительных чисел со следующими свойствами:
- длина числа не превосходит n;
- число не содержит лидирующих нулей;
- количество вхождений цифры i (0 ≤ i ≤ 9) в число не меньше a[i].
Выходные данные
В единственной строке выведите остаток от деления ответа на задачу на 1000000007 (109 + 7).
Примечание
В первом примере подходит число 9.
Во втором примере подходит число 10.
В третьем примере подходят числа: 10, 110, 210, 120, 103. Есть и другие подходящие числа, всего их 36.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
0 0 0 0 0 0 0 0 0 1
|
1
|
|
2
|
2
1 1 0 0 0 0 0 0 0 0
|
1
|
|
3
|
3
1 1 0 0 0 0 0 0 0 0
|
36
|