Let's give it up for all the health care professionals working on the front lines in the face of the COVID-19 pandemic. Many of them can be found at the Stanford-Sunnyvale Teaching Hospital (SSTH), a facility that's working tirelessly to keep the disease under control. The hospital is already following standard infection prevention and control practices, but Dr. Gregory Klaus, M.D. (one of SSTH's most brilliant doctors) is hoping to further reduce transmissions by making some renovations to the building layout.

A certain floor of the SSTH facility features \(N\) rooms (numbered from \(1\) to \(N\)) and \(N - 1\) hallways (each running directly between a pair of rooms), such that every room is reachable from every other room through a sequence of hallways. In computer science terms, the floor is organized like a tree rooted at room 1. Specifically, for each room \(i\) aside from the first (\(2 \le i \le N)\), there's a hallway running between it and room \(E_i\) that can be traversed in either direction.

Each room \(i\) contains either a patient that has been diagnosed with COVID-19 (denoted by \(S_i\) = _"#"_), or otherwise an uninfected patient (denoted by \(S_i\) = _"*"_).

With the help of the hospital's construction team, Dr. Klaus plans to renovate the floor as follows: close down one existing hallway and then construct a new one between two rooms, such that all rooms on the floor still end up reachable from all other rooms. In doing so, he would like to maximize the number of unordered pairs of uninfected patients who can safely reach each other in the resulting layout. An uninfected patient can safely reach another uninfected patient if their rooms are connected by a sequence of hallways which doesn't pass through any rooms with infected patients. It's possible that Dr. Klaus may elect to close down a hallway and then reconstruct a hallway between that same pair of rooms — the renovation budget needs to go somewhere...

For example, consider the following floor layout, with rooms 2 and 6 containing infected patients:

{{PHOTO_ID:729459790952901}}

Initially, only the uninfected patients in rooms 1 and 3 can safely reach each another. However, if Dr. Klaus were to close down the hallway between rooms 1 and 2 and construct a new one between rooms 1 and 5 (as illustrated below), then patients in any of the three pairs of rooms (1, 3), (1, 5), and (3, 5) would be able to reach one another:

{{PHOTO_ID:294725001615446}}

Klaus has just two questions: what is the maximum attainable number of such safely-reachable uninfected patient pairs, and what is the number of distinct ordered pairs of hallway closures/constructions yielding that result?

In order to reduce the size of the input, the values \(E_{2..N}\) will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(E_{2..(K+1)}\), as well as the 3 constants \(A\), \(B\), and \(C\), and must then compute the remaining values \(E_{(K+2)..N}\) as follows:

\(E_i = ((A * E_{i-2} + B * E_{i-1} + C) \text{ modulo } (i - 1)) + 1\) for \(i > K+1\)

# Input

Input begins with an integer \(T\), the number of hospital floors. For each floor, there are 4 lines.

The first line contains the 2 space-separated integers \(N\) and \(K\).

The second line contains the length-\(N\) string \(S_{1..N}\).

The third line contains the \(K\) space-separated integers \(E_{2..K+1}\).

The fourth line contains the 3 space-separated integers \(A\), \(B\), and \(C\).

# Output

For the \(i\)th hospital floor, print a line containing *"Case #i: "* followed by 2 integers, the maximum attainable number of safely-reachable uninfected patient pairs, and the number of distinct renovation plans yielding that result.

# Constraints

\(1 \le T \le 80\)
\(3 \le N \le 1,000,000\)
\(2 \le K \le N-1\)
\(S_i \in \{``*", ``\#"\}\)
\(0 \le A, B, C \le 1,000,000,000\)
\(1 \le E_i \le i-1\)

The sum of N across all floors is at most 4,000,000.

# Explanation of Sample

For the first floor, any of the following four renovation plans would result in every uninfected patient being able to safely reach every other uninfected patient (for a total of 3 pairs):

- Close hallway 1-2, construct hallway 1-2
- Close hallway 1-2, construct hallway 1-3
- Close hallway 2-3, construct hallway 1-3
- Close hallway 2-3, construct hallway 2-3

For the second floor, the same four renovation plans would all result in 0 safely-reachable uninfected patient pairs, while still ensuring that all rooms remain reachable from all other rooms.

For the third floor, only the following two renovation plans would allow the two uninfected patients to safely reach one another:

- Close hallway 1-2, construct hallway 2-3
- Close hallway 1-3, construct hallway 2-3

The fourth floor is illustrated above, including one of eight optimal renovation plans for it.

For the sixth floor, \(E_{2..N} = [1, 2, 2, 4, 3, 6, 4, 8, 5]\).