using namespace std;
typedef long long LL;
#define MAXN 1000013
#define MAXM 1000013
#define MOD 1000000007
int T;
int N, M, K;
int P[MAXN], L[MAXN], H[MAXN], X[MAXM], Y[MAXM];
vector<int> adj[MAXN];
int in[MAXN], out[MAXN], t = 0;
LL depth[MAXN];
template <typename T = int64_t>
class kinetic_tournament {
const T INF = numeric_limits<T>::max();
typedef pair<T, T> line;
size_t n; // size of the underlying array
T temp; // current temperature
vector<line> st; // tournament tree
vector<T> melt; // melting temperature of each subtree
inline T eval(const line& ln, T t) {
return ln.first * t + ln.second;
}
inline bool cmp(const line& line1, const line& line2) {
auto x = eval(line1, temp);
auto y = eval(line2, temp);
if (x != y) return x < y;
return line1.first < line2.first;
}
T next_isect(const line& line1, const line& line2) {
if (line1.first > line2.first) {
T delta = eval(line2, temp) - eval(line1, temp);
T delta_slope = line1.first - line2.first;
assert(delta > 0);
T mint = temp + (delta - 1) / delta_slope + 1;
return mint > temp ? mint : INF; // prevent overflow
}
return INF;
}
void recompute(size_t lo, size_t hi, size_t node) {
if (lo == hi || melt[node] > temp) return;
size_t mid = (lo + hi) / 2;
recompute(lo, mid, 2 * node + 1);
recompute(mid + 1, hi, 2 * node + 2);
auto line1 = st[2 * node + 1];
auto line2 = st[2 * node + 2];
if (!cmp(line1, line2))
swap(line1, line2);
st[node] = line1;
melt[node] = min(melt[2 * node + 1], melt[2 * node + 2]);
if (line1 != line2) {
T t = next_isect(line1, line2);
assert(t > temp);
melt[node] = min(melt[node], t);
}
}
void update(size_t i, T a, T b, size_t lo, size_t hi, size_t node) {
if (i < lo || i > hi) return;
if (lo == hi) {
st[node] = {a, b};
return;
}
size_t mid = (lo + hi) / 2;
update(i, a, b, lo, mid, 2 * node + 1);
update(i, a, b, mid + 1, hi, 2 * node + 2);
melt[node] = 0;
recompute(lo, hi, node);
}
T query(size_t s, size_t e, size_t lo, size_t hi, size_t node) {
if (hi < s || lo > e) return INF;
if (s <= lo && hi <= e) return eval(st[node], temp);
size_t mid = (lo + hi) / 2;
return min(query(s, e, lo, mid, 2 * node + 1),
query(s, e, mid + 1, hi, 2 * node + 2));
}
public:
// Constructor for a kinetic tournament, takes in the size n of the
// underlying arrays a[..], b[..] as input.
kinetic_tournament(size_t size) : n(size), temp(0) {
assert(size > 0);
size_t seg_size = ((size_t) 2) << (64 - __builtin_clzll(n - 1));
st.resize(seg_size, {0, INF});
melt.resize(seg_size, INF);
}
// Sets A[i] = a, B[i] = b.
void update(size_t i, T a, T b) {
update(i, a, b, 0, n - 1, 0);
}
// Returns min{s <= i <= e} A[i] * T + B[i].
T query(size_t s, size_t e) {
return query(s, e, 0, n - 1, 0);
}
// Increases the internal temperature to new_temp.
void heaten(T new_temp) {
assert(new_temp >= temp);
temp = new_temp;
recompute(0, n - 1, 0);
}
};
void read_p(int* X, int lim) {
for (int i = 0; i < K; i++)
cin >> X[i];
LL A, B, C;
cin >> A >> B >> C;
for (int i = K; i < lim; i++)
X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % i) + 1;
}
void read_input(int* X, int lim) {
for (int i = 0; i < K; i++)
cin >> X[i];
LL A, B, C, D;
cin >> A >> B >> C >> D;
for (int i = K; i < lim; i++)
X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % D) + 1;
}
void read_x(int* X, int lim, int mod) {
for (int i = 0; i < K; i++)
cin >> X[i];
LL A, B, C;
cin >> A >> B >> C;
for (int i = K; i < lim; i++)
X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % mod) + 1;
}
void dfs(int n, LL d) {
in[n] = t++;
depth[n] = d;
for (int v : adj[n]) {
dfs(v, d + L[v]);
}
out[n] = t;
}
void solve() {
cin >> N >> M >> K;
read_p(P, N);
read_input(L, N);
read_input(H, N);
read_x(X, M, N);
read_input(Y, M);
for (int i = 0; i < N; i++) {
// deallocate memory for adj
vector<int> temp;
swap(temp, adj[i]);
in[i] = out[i] = -1;
depth[i] = 0;
}
for (int i = 1; i < N; i++) {
--P[i];
adj[P[i]].push_back(i);
}
t = 0;
dfs(0, 0);
kinetic_tournament<> kt(N);
vector<pair<int, pair<bool, int> > > events;
LL ans = 1;
for (int i = 0; i < M; i++) {
--X[i];
events.push_back({Y[i], {true, i}});
}
for (int i = 0; i < N; i++) {
if (adj[i].size()) { // not a leaf
events.push_back({H[i], {false, i}});
} else { // leaf
kt.update(in[i], depth[i], 0);
}
}
sort(events.begin(), events.end());
for (auto p : events) {
int temp = p.first;
kt.heaten(temp);
if (p.second.first) { // query
int qi = p.second.second;
int n = X[qi];
LL val = kt.query(in[n], out[n] - 1) - temp * depth[n];
ans = (ans * ((val + 1) % MOD)) % MOD;
}
else { // update
int n = p.second.second;
LL val = kt.query(in[n], out[n] - 1) - temp * depth[n];
kt.update(in[n], depth[n], val);
}
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("D.txt", "r", stdin);
freopen("D.out", "w", stdout);
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cerr << tc << endl;
cout << "Case #" << tc << ": ";
solve();
}
cout.flush();
return 0;
}