After a grueling Division 2 contest, Nayeem fell asleep. The next morning, he woke up in a strange place called Borderland, where he was forced to participate in a peculiar challenge: the "Queen of Diamonds" game!
In the game arena, there is a line of $$$n$$$ bottles, each having a color label. Nayeem is armed with a special pistol. His task is to shoot and remove some (possibly none) bottles such that, in the remaining bottles, every color appears an even number of times.
Nayeem has to play multiple rounds. In each round, he will survive the game if and only if he can achieve this condition.
Your task is to determine the total number of different ways Nayeem can shoot the bottles. Two results are considered different if there is at least one bottle whose state (removed or kept) differs between them. Since the answer can be very large, output it modulo $$$1000000007$$$.
The first line of the input contains an integer $$$r$$$ ($$$1 \leq r \leq 2 \times 10^4$$$) — the number of rounds Nayeem has to play. The descriptions of $$$r$$$ rounds follow.
The first line of each round contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — the number of bottles.
The second line of each round contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters — describing the color of the bottles. The $$$i$$$-th character $$$(1 \le i \le n)$$$ of the string represents the color of the $$$i$$$-th bottle.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^6$$$.
For each round, output a single integer in a line — the total number of ways Nayeem can beat the game modulo $$$1000000007$$$.
65ababa5zzzzz6abcabc7missile11mississippi31thefiveboxingwizardsjumpquickly
8 16 8 4 128 32
The $$$8$$$ ways to beat the game for the first round are illustrated in the following diagram:
