Fast Power

Lab Java Intermediate 20 points

Write a recursive static long power(long b, int e, long mod) using squaring, and print b^e mod 1000000007.

Input

One line: b e.

Output

One integer.

Example

Input

2 10

Output

Sample input available Sample output available

Editor

Java

Hints

b^e = (b^(e/2))^2, times b once more if e is odd.

Solution explanation

Only about log₂(e) calls are needed. Underscores in numeric literals (Java 7+) improve readability.

Show solution

import java.util.Scanner;

public class Main {
    static long power(long b, int e, long mod) {
        if (e == 0) {
            return 1 % mod;
        }
        long half = power(b, e / 2, mod);
        long result = half * half % mod;
        if (e % 2 == 1) {
            result = result * (b % mod) % mod;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long b = sc.nextLong();
        int e = sc.nextInt();
        System.out.println(power(b, e, 1_000_000_007L));
    }
}

Output

Answer