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