C. Meow loves mEow loves meOw (8 Version) (Yellow)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Michelangelo has adopted $$$N$$$ mutant cats and arranged them in a circle ($$$N$$$ is a multiple of 8).

He needs to assign each cat a letter from the set [$$$m$$$, $$$e$$$, $$$o$$$, $$$w$$$, $$$M$$$, $$$E$$$, $$$O$$$, $$$W$$$] to form a continuous circular string.

The string must follow Master Splinter's strict training rules:

  1. The Base: It must be made of continuous 4-letter "meow" blocks (case-insensitive);
  2. The Capital: In every block, exactly one letter is capitalized;
  3. The Shift: The capital letter must shift exactly 1 position to the left OR 1 position to the right in the following block. (For example: if the current block is mEow, the next block must be either Meow or meOw).

You are also given $$$M$$$ constraints. Each constraint is a pair of numbers $$$(u, v)$$$, meaning the cat at index $$$u$$$ and the cat at index $$$v$$$ must be assigned the exact same character (both the letter and the case must match perfectly).

Calculate the total number of valid circular strings you can create that satisfy all the rules and all $$$M$$$ constraints.

Since the answer can be very large, output it modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — denotes the number of test cases.

for each test case:

The first line is Two space-separated integers $$$N$$$ ($$$8 \le N \le 10^5$$$) and $$$M$$$ ($$$0 \le M \le 10^5$$$) — denotes the number of cats and it is guaranteed to be a multiple of 8, and the number of constraints respectively.

The next $$$M$$$ lines: Two space-separated integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$) — denotes a constraint where the character at position $$$u$$$ must equal the character at position $$$v$$$.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.

It is guaranteed that the sum of $$$M$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print the total number of valid circular strings modulo $$$10^9 + 7$$$.

Example
Input
3
8 0
8 1
2 6
8 1
1 6
Output
8
4
0