| Codeforces Round 291 (Div. 2) |
|---|
| Закончено |
Когда Дарту Вейдеру становится скучно, он садится на диван, закрывает глаза и представляется себе бесконечное корневое дерево, в котором у каждой вершины есть ровно n сыновей, при этом для каждой вершины расстояние от неё до её i - го слева сына равняется di. Лорд ситхов любит считать количество вершин в дереве, находящихся на расстоянии не более x от корня. Под расстоянием здесь понимается сумма длин рёбер на пути между вершинами.
Для него это вошло в привычку и также стало скучным. "Но зачем тогда он это делает?" — спросите вы. Просто он чувствует превосходство, зная, что с этой задачей способен справиться только он.
Хотите бросить вызов самому Дарту Вейдеру? Посчитайте требуемое количество вершин. Так как ответ может быть большим - найдите его по модулю 109 + 7.
В первой строке через пробел записано два целых числа n и x (1 ≤ n ≤ 105, 0 ≤ x ≤ 109) — количество сыновей каждой вершины и расстояние от корня, в пределах которого требуется посчитать вершины.
В следующей строке через пробел следуют n чисел di (1 ≤ di ≤ 100) — длина ребра, соединяющего каждую вершину с её i-м сыном.
Выведите одно число — количество вершин в дереве на расстоянии от корня не более x.
3 3
1 2 3
8
Рисунок к примеру (желтым помечены вершины, расстояние до которых не больше трех)
