Назовем массив \(a\) из \(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
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач