Назовем массив \(a\) из \(n\) неотрицательных целых чиселкрасивым, если выполняются следующие условия:
- массив содержит хотя бы одно из чисел \(x\), \(x + 1\), ..., \(x+k-1\);
- последовательные элементы массива отличаются не более чем на \(k\) (т.е. \(|a_i-a_{i-1}| \le k\) для каждого \(i \in [2, n]\)).
Даны значения \(n\), \(x\) и \(k\). Ваша задача — посчитать количество красивых массивов длины \(n\). Поскольку ответ может быть большим, выведите его по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество красивых массивов длины \(n\), взятое по модулю \(10^9+7\).
Примечание
В первом наборе входных данных примера следующие массивы являются красивыми:
- \([0, 0, 0]\);
- \([0, 0, 1]\);
- \([0, 1, 0]\);
- \([0, 1, 1]\);
- \([0, 1, 2]\);
- \([1, 0, 0]\);
- \([1, 0, 1]\);
- \([1, 1, 0]\);
- \([2, 1, 0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 0 1
1 4 25
4 7 2
1000000000 40 1000000000
|
9
25
582
514035484
|