F. Красивые массивы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем массив $$$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$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных.

Единственная строка каждого набора содержит три целых числа $$$n$$$, $$$x$$$ и $$$k$$$ ($$$1 \le n, k \le 10^9$$$; $$$0 \le x \le 40$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество красивых массивов длины $$$n$$$, взятое по модулю $$$10^9+7$$$.

Пример
Входные данные
4
3 0 1
1 4 25
4 7 2
1000000000 40 1000000000
Выходные данные
9
25
582
514035484
Примечание

В первом наборе входных данных примера следующие массивы являются красивыми:

  • $$$[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]$$$.