## Or-Xor-And

**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