#ifndef MODH
#define MODH

#include <inttypes.h>
#include <assert.h>

typedef int64_t num;
extern num p;

num Extended_Euclid(num a, num b, num *x, num *y);

inline num mod(num a, num b) {
#ifndef NOPRIME
	num m = 0;
	num n = a;

	//num r = (a + b) % b;

	//num r = a % b;
	//r = r < 0 ? r + b : r;

	n += b;

	for (m = n; n > b; n = m) {
		for (m = 0; n; n >>= 31) {
			m += n & b;
		}
	}

	m = m == b ? 0 : m;

	//if (m != r) {
	//	printf("a: %"PRId64", b: %"PRId64"\n", a, b);
	//	printf("m: %"PRId64", r: %"PRId64"\n", m, r);
	//	//exit(EXIT_FAILURE);
	//}

	return m;
#else
	num r = (a + b) % b;
	//num r = a % b;
	//r = r < 0 ? r + b : r;
	return r;
#endif
}

inline num mulmod(num a, num b) {
	assert(a >= 0);
	assert(b >= 0);

	assert(a < 2147483647);
	assert(b < 2147483647);

	num r = mod((a * b), p);

	assert(r >= 0);
	return r;
}

inline num addmod(num a, num b) {
	assert(a >= 0);
	assert(b >= 0);

	assert(a < 2147483647);
	assert(b < 2147483647);

	num r = mod((a + b), p);
	assert(r >= 0);
	return r;
}

inline num submod(num a, num b) {
	assert(a >= 0);
	assert(b >= 0);

	assert(a < 2147483647);
	assert(b < 2147483647);

	num r = mod((a - b), p);
	assert(r >= 0);
	return r;
}

inline num divmod(num a, num b) {
	assert(a >= 0);
	assert(b >= 0);

	assert(a < 2147483647);
	assert(b < 2147483647);

	num q1, q2;

	Extended_Euclid(b, p, &q1, &q2);

	q1 = mod(q1, p);
	assert(q1 >= 0);

	num r =  mulmod(a, q1);

	assert(r >= 0);
	return r;
}

#endif
