Первыми словами маленького Бадави были «AND 0 большая сумма», поэтому он решил решить следующую задачу. Даны два целых числа \(n\) и \(k\), вычислите количество массивов длины \(n\), таких что:
Так как ответ может быть очень большим, выведите его остаток от деления на \(10^9+7\).
В первой строке находится одно целое число \(t\) (\(1 \le t \le 10\)) — количество наборов входных данных.
В единственной строке каждого набора входных данных даны два целых числа \(n\) и \(k\) (\(1 \le n \le 10^{5}\), \(1 \le k \le 20\)).
Для каждого набора входных данных выведите количество массивов, удовлетворяющих всем условиям. Так как ответ может быть большим, выведите его остаток от деления на \(10^9+7\).
В первом примере подходят \(4\) массива:
2 2 2 100000 20
4 226732710
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач