Inverse of a Function

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/MARCH20/hindi/INVXOR.pdf), [Bengali](http://www.codechef.com/download/translated/MARCH20/bengali/INVXOR.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/MARCH20/mandarin/INVXOR.pdf), [Russian](http://www.codechef.com/download/translated/MARCH20/russian/INVXOR.pdf), and [Vietnamese](http://www.codechef.com/download/translated/MARCH20/vietnamese/INVXOR.pdf) as well. The *beauty* of a sequence of nonnegative integers is computed in the following way: for each of its nonempty (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 nonnegative integer sequences with length $N$ which have beauty $B$. You are given three integers $N$, $X$ and $M$. Find the smallest nonnegative 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 spaceseparated 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 \le T \le 100$  $1 \le N \le 10^{10,000}$  $1 \le M \le 10^9$  $0 \le X \lt M$ ### Subtasks **Subtask #1 (45 points):**  $N \le 10^9$  $M \le 10^5$ **Subtask #2 (55 points):** original constraints ### Example Input ``` 3 2 2 7 4 3 17 3 5 13 ``` ### Example Output ``` 6 1 28 ```Author:  sjshohag 
Editorial  https://discuss.codechef.com/problems/INVXOR 
Tags  combinatorics, discretelogarithm, march20, mediumhard, sjshohag, tmwilliamlin 
Date Added:  24012020 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 