Question

Given a number represented exponentially, calculate it's value.
The number might be very large so print out its value mod 91.

Input Format

First line is the number (n) of exponentials you will have to calculate.
The next n lines will each contain two values (b and e), the base value and the exponent.

Constraints

All input values will be valid java integers. n will be > 0
b will be > 0 and <= 10000
e will be >= 0

Output Format

Output n values, the solutions for each of the n exponents you are given.

Sample Input 0

3
13 3
76 3
100 3
Sample Output 0

13
83
1
Explanation 0

13^3 = 13 * 13 * 13 = 2197
2197 mod 91 = 13
76^3 = 76 * 76 * 76 = 483,976
483,976 mod 91 = 83
100^3 = 100 * 100 * 100 = 1,000,000
1,000,000 mod 91 = 1

Sample Input 1

6
90 3
66 3
90 3
80 4
28 4
90 4
Sample Output 1

90
27
90
81
42
1

Answer 1

Program Code Screenshot :

Sample Output :

Program Code to Copy

import java.util.Scanner;

class Main{

    static int pow(int b, int e, int m){
        //If exponent is 0, return 1
        if(e==0){
            return 1;
        }
        //Find b^(e/2)
        int ans = pow(b,e/2,m);
        ans = (ans*ans)%m;
        //Deal with odd exponent
        if(e%2==1){
            ans = (ans*b)%m;
        }
        return ans;
    }

    public static void main(String[] args) {
        //Scanner to read user input
        Scanner obj = new Scanner(System.in);
        int n = obj.nextInt();
        //Read all base and exponent and print results
        for(int i=0;i<n;i++){
            int b = obj.nextInt();
            int e = obj.nextInt();
            System.out.println(pow(b,e,91));

        }
    }
}