pub fn powermod(n: u64, p: u64, m: u64) -> u64 {
	if p == 0 { return 1 % m }
	if p == 1 { return n % m }

	let mut r = powermod(n, p / 2, m);

	r = r * r % m;
	if p & 1 == 1 {
		r = r * n % m;
	}
	
	r
}

#[test]
fn test_powermod() {
	assert_eq!(powermod(2, 999999, 147), 50);
}