#include <iostream>
#include <stdlib.h>

long int modexp(long int base, long int exponent, long int modulus){
	int result = 1;
	base = base % modulus;
	while(exponent > 0){
		if(exponent % 2 == 1)
			result = (result*base) % modulus;
		exponent = exponent >> 1;
		base = (base*base) % modulus;
	}
	return result;
}

int main(){
	std::cout << modexp(7, 397395439, 9) << std::endl;
}