## Or-Xor-And

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 (called or-xor-and) as a binary operation that takes as input two operands and returns as output (A|B) ^ (A&B).

| is the bitwise operator, ^ is the bitwise operator, and & is the bitwise operator. The ^ operator returns true on two boolean operands if one operand is true and the other is false. A bitwise operator performed on two binary strings of length returns a binary string of length such that , where are the th bits, starting from the right, of 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 , of length , is defined as

for where is the th bit of starting from the right and and are bits given as input.

Count the number of ordered pairs of binary strings , each of length , such that is equal to . Output the answer modulo .

#### Constraints

For all subtasks,

.

Subtask Points Additional Constraints
No additional constraints

#### Input Specification

The first line of input contains one integer: .

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

#### Output Specification

Output the answer modulo on a single line.

#### Sample Input

3
0 1

#### Sample Output

8

#### Explaination

The binary string is 110. The ordered pairs of binary strings such that , sorted lexicographically, are 000110, 001111, 010100, 011101, 100010, 101011, 110000, and 111001.

## Comments

There are no comments at the moment.