Не взнавши імені дівчини у попередній задачі, Саша вирішив навести довідки, благо база дани університету і ВКонтакті завжди під рукою. Виявилось, що Іра --- вже чотири рокм як відмінниця --- твердо вирішила отримати степінь бакалавра, і, як вияснилось потім, степінь магістра та степінь кандидата наук. І мало що ще далі?.. --- \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} .