Modular Exponentiation

You are given an array queries, where each queries[i] = [a, b] asks for the value of a^b modulo 10^9 + 7.

By convention, 0^0 = 1.

Return an array with one answer per query, in order.

Examples

Example 1

Input: queries = [[3,4],[2,8],[123,123]]
Output: [81,256,921450052]
Explanation: 3^4 = 81 and 2^8 = 256 are below the modulus; 123^123 is reduced modulo 10^9 + 7.

Example 2

Input: queries = [[0,0],[0,5],[5,0]]
Output: [1,0,1]
Explanation: 0^0 is defined as 1, 0^5 = 0, and 5^0 = 1.