Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

The *beauty* of a sequence of non-negative integers is computed in the following way: for each of its non-empty (not necessarily contiguous) subsequences, compute the XOR of all elements of this subsequence; then, sum up all the XORs you obtained.

Let $F(N, B)$ denotes the number of non-negative integer sequences with length $N$ which have beauty $B$. You are given three integers $N$, $X$ and $M$. Find the smallest non-negative integer $B$ such that $F(N, B) \bmod M = X$, or determine that there is no such $B$. Since even the smallest such $B$ might be very large, compute its remainder modulo $998,244,353$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains three space-separated integers $N$, $X$ and $M$.

------  Output ------
For each test case, print a single line containing one integer ― the smallest valid $B$ (modulo $998,244,353$), or $-1$ if there is no valid $B$.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{10,000}$
$1 ≤ M ≤ 10^{9}$
$0 ≤ X < M$

------  Subtasks ------
Subtask #1 (45 points):
$N ≤ 10^{9}$
$M ≤ 10^{5}$

Subtask #2 (55 points): original constraints

----- Sample Input 1 ------ 
3

2 2 7

4 3 17

3 5 13
----- Sample Output 1 ------ 
6

-1

28

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Combinatorics

Mathematics


Solutions:
from math import gcd, sqrt
modul = 998244353

def modiFun(a, b, p):
	a %= p
	b %= p
	if b == 1:
		return 0
	(count, t, g) = (0, 1, gcd(a, p))
	while g != 1:
		if b % g:
			return -1
		p = p // g
		b = b // g
		t = int(int(int(t * a) // g) % p)
		count += 1
		if b == t:
			return count
		g = gcd(a, p)
	(hash, base, m) = ({}, b, int(sqrt(1.0 * p) + 1))
	for i in range(m):
		hash[base] = i
		base = base * a % p
	(base, temp) = (pow(a, m, p), t)
	for i in range(1, m + 2):
		temp = temp * base % p
		if temp in hash.keys():
			return i * m - hash[temp] + count
	return -1
for _ in range(int(input())):
	(n, x, m) = map(int, input().split())
	if 1 % m == x:
		print(0)
		continue
	if x == 0 and m == 1:
		print(0)
		continue
	if x == 0 and n != 1:
		print(1)
		continue
	var = (pow(2, n, m) - 1 + m) % m
	power = modiFun(var, x, m)
	if power == -1:
		print(-1)
		continue
	answ = pow(2, n - 1, modul) * (pow(2, power, modul) - 1 + modul) % modul % modul
	if answ == 0:
		if 1 % m != x:
			answ = -1
	if answ == 1:
		if 1 % m != x or n != -1:
			answ -= 1
	print(answ)


modulo = 998244353

def mod_inv(a: int, n: int) -> int:
	(p, q, b) = (1, 0, n)
	while b:
		c = a // b
		(a, b) = (b, a % b)
		(p, q) = (q, p - c * q)
	if a != 1:
		raise ValueError(f'{a} is not invertible modulo {n}')
	return p if p >= 0 else p + n

def factorize(n):
	factors = {}
	if n & 1 == 0:
		e = 0
		while n & 1 == 0:
			n >>= 1
			e += 1
		factors[2] = e
	p = 3
	while True:
		if p * p > n:
			break
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			factors[p] = e
		p += 2
	if n > 1:
		factors[n] = 1
	return factors

def bs_gs(a, b, m, phi_m):
	n = int(phi_m ** 0.5)
	inv_a = mod_inv(a, m)
	dp = {}
	p = b
	an = pow(a, n, m)
	for r in range(n):
		if p not in dp:
			dp[p] = r
		p = p * inv_a % m
	left = 1
	for q in range(phi_m // n + 1):
		if left in dp:
			return q * n + dp[left]
		left = left * an % m
	return -1

def dl(a, b, m):
	a %= m
	b %= m
	if b == 1:
		return 0
	factors_m = factorize(m)
	common_a = {}
	common_b = {}
	aa = a
	bb = b
	for (p, em) in factors_m.items():
		ea = 0
		if aa != 0:
			while aa % p == 0:
				ea += 1
				aa //= p
		else:
			ea = em
		eb = 0
		if b != 0:
			while bb % p == 0:
				eb += 1
				bb //= p
		else:
			eb = em
		if ea > 0 and eb == 0 or (ea == 0 and eb > 0):
			return -1
		if ea:
			common_a[p] = ea
		if eb:
			common_b[p] = eb
	for (p, eb) in common_b.items():
		if eb < factors_m[p]:
			if eb % common_a[p]:
				return -1
			x = eb // common_a[p]
			if pow(a, x, m) != b:
				return -1
			return x
	x_min = 0
	for (p, ea) in common_a.items():
		em = factors_m[p]
		eb = common_b[p]
		m //= p ** em
		x_min = max(x_min, (em + ea - 1) // ea)
	left = pow(aa, x_min, m)
	right = 1
	for (p, ea) in common_a.items():
		em = factors_m.pop(p)
		eb = common_b[p]
		left = left * p ** (ea * x_min - em) % m
		right = right * p ** (eb - em)
	right %= m
	b = mod_inv(left, m) * right * bb % m
	phi_m = 1
	for (p, e) in factors_m.items():
		phi_m *= (p - 1) * p ** (e - 1)
	ret = bs_gs(a, b, m, phi_m)
	if ret == -1:
		return -1
	return ret + x_min

def solve_v1(n, x, m):
	y = (pow(2, n, m) - 1) % m
	p = 1
	for l in range(m):
		if p == x:
			return (pow(2, l, modulo) - 1) * pow(2, n - 1, modulo) % modulo
		p = p * y % m
	return -1

def solve_v2(n, x, m):
	if m == 1:
		return 0
	if x == 0:
		if n == 1:
			return -1
		return 1
	y = (pow(2, n, m) - 1) % m
	l = dl(y, x, m)
	if l == -1:
		return -1
	return (pow(2, l, modulo) - 1) * pow(2, (n - 1) % (modulo - 1), modulo) % modulo
T = int(input())
for _ in range(T):
	(N, X, M) = map(int, input().strip().split())
	print(solve_v2(N, X, M))