Time limit: 0.5s
Memory limit: 128MB
Input:
Output:
Given the natural number and the binary strings of length : and ().
Task
Find how many pairs satisfy the following criteria:
Where represents the XOR operation on bits, and represents the AND operation on bits.
Input data
The first line contains the number . The second line contains the number in base . The third line contains the number in base .
Output data
The first line contains a single natural number, representing the answer, modulo .
Constraints and clarifications
Example
stdin
4
0100
1101
stdout
18
Explanation
There are pairs of natural numbers that meet the conditions. These pairs are:
, therefore the answer is .