int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

pair<int64_t, int64_t> E(int64_t a, int64_t b) {
	// {x, y}   ax    +    by
	//        |x|<b       |y|<a
 	if (!b)
		return {1, 0}; // 1*a+0*b=a
	auto [x1, y1] = E(b, a % b);
	// a%b = a - k*b | k=a/b
	// b*x1 + (a%b)*y1 = gcd
	// b*y  + a*x = gcd
	return {y1, x1 - k*y1};
}
int64_t Inv(int64_t a, int64_t m) {
	auto [x, y] = E(a, m);
	return x < 0 ? x + m : x; // |x|<m
	// 1 <= x < m

	// return a * x + m * y == 1 ? x : 0;
}

// Умножение
// 1. x^n через log умножений (*, n раз)
// 2. x*n через log сложений  (+, n раз)
//    63-битные

// 10-байт | g++, clang
// 128-битный
long double mul(uint64_t a, uint64_t b, uint64_t m) {
	uint64_t ik = (long double)a * b / m;
	// a * b = ik * m + rest
	int64_t r = a * b - ik * m; // mod 2^{64}
	if (r < 0) r += m;
	if (r >= m) r -= m;
	return r;
}