Gus is given a binary string . He has to perform the following operation exactly once:
Choose some subsequence of the string. Then, arrange characters on those positions in the sorted order.
For example, for string 011010110 Gus can choose symbols at positions 3, 4, 6, 7, 9 (underlined). Symbols at these positions form string 10010. After sorting them, Gus will get the string 010010111.
Gus wants to find the number of possible strings he might get after applying this operation exactly once. For him this problem is trivial, but can you solve it?
As this number can be very large, output it modulo .
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases. The description of test cases follows.
The only line of each test case contains a binary string .
It is guaranteed that the sum of lengths of over all test cases does not exceed 10^6.
For each test case, output a single integer — the number of possible strings Gus might get after applying this operation exactly once.
Example
For the fourth test case, the string is 10. If he selects both positions, he will get string 01. For any other selection, the string will remain 10. So, there are two possible strings he might obtain.
For the fifth test case, here are all possible strings: 1010, 0011, 0110, 1001.