// Arup Guha
// 2/1/2014
// Example of fast modular exponentiation.

import java.util.*;
import java.math.*;

public class fastmodexpo {

	public static void main(String[] args) {

		// Try test with both our method and Java's BigInteger.
		System.out.println(modPow(987654321L, 1000000000000000000L, 1000000007L));
		BigInteger b = new BigInteger("987654321");
		BigInteger e = new BigInteger("1000000000000000000");
		BigInteger m = new BigInteger("1000000007");
		System.out.println(b.modPow(e,m));
	}

	// Calculates base^exp mod mod.
	public static long modPow(long base, long exp, long mod) {

		// Base cases.
		if (exp == 0L) return 1L;
		if (exp == 1L) return base%mod;

		// Time savings here - even exponent case.
		if (exp%2L == 0) {
			long tmp = modPow(base, exp/2, mod);
			return tmp*tmp%mod;
		}

		// Usual recursive breakdown for odd case.
		else {
			return (modPow(base, exp-1, mod)*base)%mod;
		}
	}
}