## 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 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.