The first line of input contains a single integer 'T', representing the number of test cases. The first line of each test contains three space-separated integers 'X', 'N', and 'M'.
For each test case, return a single line containing the value of ('X' ^ 'N') % 'M'.
You don't need to print anything, it has already been taken care of. Just implement the given function.
Can you solve the problem in O(log 'N') time complexity and O(1) space complexity?
1 <= T <= 100 1 <= X, N, M <= 10^9 Time limit: 1 sec
In this solution, we will run a loop from 1 to ‘N’ and each time we will multiply ‘X’ to our current product and take modulo of current product with ‘M’.
Make sure to convert variable in long long during multiplication to avoid integer overflow.
Eg. (10^8 * 10^8) % 10^9 will result in an integer overflow so we will convert it in long long form by multiplying it with 1LL. We need to do (1LL*10^8*10^8)%10^9 to get the correct answer.
The steps are as follows: