Karim Meets Gollum

কুয়াশার পাহাড়ে বিলবো আংটি খুঁজে পেয়েছে শুনে হবিট করিম পাহাড়ে গেল আরো গুপ্তধনের খোঁজে। কিন্তু কুয়াশার পাহাড়ে গিয়েই সে পড়ল গোলেমের সামনে। বিলবো তার আংটি চুরি করেছে বলে গোলেমের হবিটদের উপর অনেক রাগ। গোলেমের আবার ধাঁধা খুব পছন্দ। সে করিমকে কয়েকটা প্রশ্ন ধরিয়ে দিয়ে বলল, না পারলে ওকে একেবারে মেরেই ফেলবে!

প্রতিটি প্রশ্নে গোলেম করিমকে দুইটি পূর্ণ সংখ্যা $N$ এবং $K$ বলে দেয়। তার উত্তরে করিমকে $N$ এর সকল ধনাত্মক উৎপাদকের $K$ তম ঘাতের যোগফল mod $(10^9 + 7)$ তে বলতে হবে। অর্থাৎ $\displaystyle \sum_{d|N} d^{K} \textbf{mod} (10^{9}+7)$ বলতে হবে।

করিম খুব সাধারণ এক হবিট, অত অংক-টংক পারে না, তাই তোমার সাহায্য দরকার ওর। গোলেমের নিষ্ঠুরতা থেকে করিমের জীবন বাঁচাতে পারবে তুমি?

Input

প্রথম লাইনে একটি পূর্ণ সংখ্যা $Q \leq 20 $ যেখানে $Q$ হল গোলেম করিমকে যতগুলো প্রশ্ন জিজ্ঞেস করবে তার সংখ্যা।
পরবর্তী $Q$ লাইনে দুইটি করে পূর্ণ সংখ্যা $N \leq 10^{16}$ এবং $K \leq 10^{18}$ থাকবে।

প্রথম সাবটাস্কের জন্য: (5 পয়েন্ট)
$ 1 \leq N \leq 10^{8}$ এবং $0 \leq K \leq 25$

দ্বিতীয় সাবটাস্কের জন্য: (10 পয়েন্ট)
$1 \leq N \leq 10^{8}$ এবং $0 \leq K \leq 10^{18}$

তৃতীয় সাবটাস্কের জন্য: (85 পয়েন্ট)
$1\leq N \leq 10^{16}$ এবং $0 \leq K \leq 10^{18}$

সকল সাবটাস্কের জন্যই $1\leq Q \leq 20 $

Output

প্রতিটি প্রশ্নের উত্তর আলাদা আলাদা লাইনে প্রিন্ট করতে হবে।

Sample

Input	Output
6 2 11 6 4 3 7 1 100 11 21 30 5	2049 1394 2188 1 410854020 25170552
For Case 1: $1^{11}+2^{11}=2049$ For Case 2: $1^{4}+2^{4}+3^{4}+6^{4}=1394$ For Case 3: $1^{7}+3^{7}=2188$ For Case 4: $1^{100}=1$ For Case 5: $1^{21}+11^{21} = 410854020$ For Case 6: $1^{5}+2^{5}+3^{5}+5^{5}+6^{5}+10^{5}+15^{5}+30^{5}=25170552$\ Note that all values are provided in modulo $(10^9+7)$

Notes:

If you are going to use python, please select pypy as language.
PyPy 7.1 (2.7) for Python 2.7 and
PyPy 7.1 (3.6) for Python 3.7.