#P17806. [ICPC 2019 Nanchang R] And and Pair
[ICPC 2019 Nanchang R] And and Pair
Problem Description
Given an extremely large non-negative integer , you are asked to count the number of pairs of integers satisfying the following conditions:
- ;
- ; and
- .
Here & represents the bitwise AND operator.
For simplicity, the binary representation of will be given. Meanwhile, you only need to output the answer modulo .
Input Format
The first line contains an integer indicating the number of test cases.
Each of the following lines contains a string which is the binary representation of the non-negative integer . Note that leading zeros of could appear in the input.
Output Format
For each test case, output a line containing the answer described above modulo .
2
111
1010
14
15