C. The Ancient Wizards' Capes

There are 𝑛

 wizards in a row numbered 1

 to 𝑛

 from left to right. Each wizard has an invisibility cape which can be worn either on his left side or on his right side. Harry walks from the position of wizard 1

 until the position of wizard 𝑛

 (1≤𝑛≤10

5

), and registers how many wizards he sees from each wizard's position. A wizard in position 𝑗

 is visible from position 𝑖

 if:

• Wizard 𝑗
•  wears his cape on his left side and 𝑖≥𝑗
• .
• Wizard 𝑗
•  wears his cape on his right side and 𝑖≤𝑗
• .

In particular, note that wizard 𝑖

 is visible from position 𝑖

.

Harry's list is very old but, after much work, you managed to decipher it. The list is an array 𝑎

 of 𝑛

 elements, where the 𝑖

-th element 𝑎

𝑖

 (1≤𝑎

𝑖

≤𝑛

) is the number of wizards that Harry saw from the position of wizard 𝑖

.

Your task is to determine how many of all the possible cape arrangements that Harry could have seen are consistent with the data recorded by the list, modulo 676767677

.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡

 (1≤𝑡≤10

4

). The description of the test cases follows.

The first line of each test case contains a single integer 𝑛

 (1≤𝑛≤10

5

) — the length of 𝑎

.

The second line contains 𝑛

 integers 𝑎

1

,𝑎

2

,…,𝑎

𝑛

 (1≤𝑎

𝑖

≤𝑛

) — the elements of 𝑎

.

It is guaranteed that the sum of 𝑛

 over all test cases does not exceed 10

5

.

Output

For each test case, print one integer — the number of arrangements for the wizards' capes that satisfy the condition, modulo 676767677

.

Example

Input

Copy

7
1
1
4
4 4 3 2
3
1 3 2
2
2 1
3
2 2 2
3
3 2 3
3
3 2 2

Output

Copy

2
1
0
1
2
0
0

Note

The image below shows an arrangement of capes that matches Harry's list in the second test case.

Wizard 1 has the invisibility cape on his left side, while wizards 2

, 3

, and 4

 wear it on their right side.

• From position 1
• , we can see wizards 1
• , 2
• , 3
• , and 4
• .
• From position 2
• , we can see wizards 1
• , 2
• , 3
• , and 4
• .
• From position 3
• , we can see wizards 1
• , 3
• , and 4
• .
• From position 4
• , we can see wizards 1
•  and 4
• .

Thus, Harry's list ends up being [4,4,3,2]

. It can be proved that this is the only possible arrangement.

In the third test case, it can be proved that Harry could not have obtained his list from any cape arrangement.

In the fifth case, note that there are two possible cape arrangements from which Harry could have gotten his list:

• 1∣∣23∣
• ∣12∣∣3