Не узнав имени девушки в предыдущей задаче, Саша решил навести справки, благо база данных университета и ВКонтакте всегда под рукой. Оказалось, что Ира --- уже четыре года как отличница --- твердо хотела получить степень бакалавра, и, как выяснилось впоследствии, степень магистра и степень кандидата наук. И мало ли что дальше?.. --- \textit{Сколько же это будет в сумме}? --- с восторгом думал Саша, при этом подсознательно вспоминая задачу с недавнего контеста, которую он так и не решил: даны два числа \textbf{N} и \textbf{K}, вычислить \includegraphics{https://static.e-olymp.com/content/bb/bb6cfd02c724d122569ca196cc4dba49c5942363.jpg} \InputFile В первой строке дано число \textbf{Q} (\textbf{1} ≤ \textbf{Q} ≤ \textbf{41000}) --- количество запросов. В каждой из \textbf{Q} следующих строк даны два числа \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^9}) и \textbf{K }(\textbf{1} ≤ \textbf{K} ≤ \textbf{1000}). \OutputFile Для каждого запроса в отдельной строке вывести одно число --- сумму \textbf{K}-ых степеней натуральных чисел от \textbf{1} до \textbf{N} по модулю \textbf{1000000007} .