超時-一道關於大數冪運算的題目，c語言實現

一道關於大數冪運算的題目，c語言實現

題目描述
冪運算是常見的數學運算之一，其原理是用同一個數相乘多次，但是有的時候當冪指數特別大的時候，這樣的運算就太浪費時間。請大家學會在冪中加特技，讓冪運算的效率提高到可以接受的程度。
輸入：
第一個行一個整數T，表示有T組數據
每組數據，輸入x，y 求x的y次冪 （2≤ x ,y≤10^9）
輸出：
每組數據輸出一個整數，表示冪運算對1000000007取模後的結果
樣例輸入：
2
2 4
2 100000000
樣例輸出：
16
494499948
我的代碼總是超時，求好方法！！謝謝！！

最佳回答：

不知道你怎麼算的
我們知道
a^m可以視作a^p*a^q（p+q=m）
而如果p=m，顯然，我們只要算了a^p，就可以再平方下就是最後的結果了。
因此最簡單的做法就是，將指數轉化成2的冪相加的結果，這相當於二進制計算，比如100000000
就是101111101011110000100000000（2）
那麼就是256+8192+16384+32768+65536+262144+1048576+...
然後我們分別計算N的這些次方的冪，別忘了，我們可以通過平方翻倍很快算出來。
最後再把結果相乘。