Or-Xor-And


Submit solution

Points: 7 (partial)
Time limit: 10.0s
Memory limit: 256M

Author:
Problem type

The time limit for this question is 10 seconds.

Define the bitwise binary operation \circledast (called or-xor-and) as a binary operation that takes as input two operands A \circledast B and returns as output (A|B) ^ (A&B).

| is the bitwise OR operator, ^ is the bitwise XOR operator, and & is the bitwise AND operator. The ^ operator returns true on two boolean operands if one operand is true and the other is false. A bitwise operator \circ performed on two binary strings A \circ B of length k returns a binary string C of length k such that C_j = A_j \circ B_j \; (1 \leq j \leq k), where A_j, B_j, C_j are the jth bits, starting from the right, of A, B, C respectively. For example, 1011^0101 is equal to 1^0 0^1 1^0 1^1, which is the binary string 1110.

The binary string s, of length N, is defined as

\displaystyle 
s_i =
\begin{cases} 
    a \quad & i=1 \\
    b \quad & i=2 \\
    s_{i-1} \circledast s_{i-2} \quad & 3 \leq i \leq N
\end{cases}

for 1 \leq i \leq N, where s_i is the ith bit of s starting from the right and a and b are bits given as input.

Count the number of ordered pairs of binary strings (x, y), each of length N, such that x \circledast y is equal to s. Output the answer modulo 998244523.

Constraints

For all subtasks,

2 \leq N \leq 10^{12},

a, b \in \{0, 1\}.

Subtask Points Additional Constraints
1 10 N \leq 6
2 50 N \leq 2 \times 10^5
3 40 No additional constraints

Input Specification

The first line of input contains one integer: N.

The next line contains two space-separated bits: a and b.

Output Specification

Output the answer modulo 998244523 on a single line.

Sample Input

3
0 1

Sample Output

8

Explaination

The binary string s is 110. The 8 ordered pairs of binary strings (x, y) such that x \circledast y = s, sorted lexicographically, are (000, 110), (001, 111), (010, 100), (011, 101), (100, 010), (101, 011), (110, 000), and (111, 001).


Comments

There are no comments at the moment.