#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7;
const int MAX = 5e8 + 25;
int arr[MAX];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for (int tst = 0; tst < t; tst++) {
memset(arr, 0, sizeof arr);
ll xx = -1;
ll n, k, w, al, bl, cl, dl, ah, bh, ch, dh;
cin >> n >> k >> w;
vector<ll> l(n), h(n);
for (int i = 0; i < k; i++)
cin >> l[i];
cin >> al >> bl >> cl >> dl;
for (int i = 0; i < k; i++)
cin >> h[i];
cin >> ah >> bh >> ch >> dh;
for (int i = 0; i < k; i++) {
l[i] = l[i] % dl;
h[i] = h[i] % dh;
}
al %= dl;
bl %= dl;
cl %= dl;
ah %= dh;
bh %= dh;
ch %= dh;
for (int i = k; i < n; i++) {
l[i] = (((al * l[i - 2]) % dl + (bl * l[i - 1]) % dl + cl) % dl) + 1;
h[i] = (((ah * h[i - 2]) % dh + (bh * h[i - 1]) % dh + ch) % dh) + 1;
}
ll ans = 1;
ll _tmp = 0;
vector<int> check;
bool check2 = 0;
for (int i = 0; i < n; i++) {
xx = max(xx, l[i] + w);
for (int j = l[i]; j <= xx; j++)
arr[j] = max((ll)arr[j], h[i]);
ll p = 0, cnt = 0;
for (int kk = l[0]; kk <= xx + 1; kk++) {
if (arr[kk] == 0 && cnt != 0) {
p += cnt - 1;
cnt = 0;
}
if (arr[kk] != 0)
cnt++;
}
p += arr[l[0]];
if (i != 0) {
if (l[i - 1] + w + 1 == l[i]) {
_tmp += h[i - 1] - 1 + h[i];
check.push_back(l[i - 1] + w);
check2 = 1;
}
}
int iii = 0;
for (int kk = l[0]; kk <= xx + 1; kk++) {
if (check2 && iii < check.size()) {
if (check[iii] == kk) {
iii++;
continue;
}
}
if (arr[kk] != arr[kk + 1]) {
int tmp = arr[kk + 1] - arr[kk];
p += abs(tmp);
if (arr[kk + 1] != 0 && tmp < 0)
p++;
else if (arr[kk] != 0 && tmp > 0)
p++;
}
else if (arr[kk] != 0)
p++;
}
_tmp %= MOD;
p += _tmp;
p %= MOD;
ans *= p;
ans %= MOD;
}
ans = (ans + MOD) % MOD;
cout << "Case #" << tst + 1 << ": " << ans << '\n';
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7Cgpjb25zdCBsbCBNT0QgPSAxZTkgKyA3Owpjb25zdCBpbnQgTUFYID0gNWU4ICsgMjU7CgppbnQgYXJyW01BWF07CgppbnQgbWFpbigpIHsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKDApOwoJY291dC50aWUoMCk7CglpbnQgdDsKCWNpbiA+PiB0OwoJZm9yIChpbnQgdHN0ID0gMDsgdHN0IDwgdDsgdHN0KyspIHsKCQltZW1zZXQoYXJyLCAwLCBzaXplb2YgYXJyKTsKCQlsbCB4eCA9IC0xOwoJCWxsIG4sIGssIHcsIGFsLCBibCwgY2wsIGRsLCBhaCwgYmgsIGNoLCBkaDsKCQljaW4gPj4gbiA+PiBrID4+IHc7CgkJdmVjdG9yPGxsPiBsKG4pLCBoKG4pOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgazsgaSsrKQoJCQljaW4gPj4gbFtpXTsKCQljaW4gPj4gYWwgPj4gYmwgPj4gY2wgPj4gZGw7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBrOyBpKyspCgkJCWNpbiA+PiBoW2ldOwoJCWNpbiA+PiBhaCA+PiBiaCA+PiBjaCA+PiBkaDsKCQlmb3IgKGludCBpID0gMDsgaSA8IGs7IGkrKykgewoJCQlsW2ldID0gbFtpXSAlIGRsOwoJCQloW2ldID0gaFtpXSAlIGRoOwoJCX0KCQlhbCAlPSBkbDsKCQlibCAlPSBkbDsKCQljbCAlPSBkbDsKCQlhaCAlPSBkaDsKCQliaCAlPSBkaDsKCQljaCAlPSBkaDsKCQlmb3IgKGludCBpID0gazsgaSA8IG47IGkrKykgewoJCQlsW2ldID0gKCgoYWwgKiBsW2kgLSAyXSkgJSBkbCArIChibCAqIGxbaSAtIDFdKSAlIGRsICsgY2wpICUgZGwpICsgMTsKCQkJaFtpXSA9ICgoKGFoICogaFtpIC0gMl0pICUgZGggKyAoYmggKiBoW2kgLSAxXSkgJSBkaCArIGNoKSAlIGRoKSArIDE7CgkJfQoJCWxsIGFucyA9IDE7CgkJbGwgX3RtcCA9IDA7CgkJdmVjdG9yPGludD4gY2hlY2s7CgkJYm9vbCBjaGVjazIgPSAwOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJCXh4ID0gbWF4KHh4LCBsW2ldICsgdyk7CgkJCWZvciAoaW50IGogPSBsW2ldOyBqIDw9IHh4OyBqKyspCgkJCQlhcnJbal0gPSBtYXgoKGxsKWFycltqXSwgaFtpXSk7CgkJCWxsIHAgPSAwLCBjbnQgPSAwOwoJCQlmb3IgKGludCBrayA9IGxbMF07IGtrIDw9IHh4ICsgMTsga2srKykgewoJCQkJaWYgKGFycltra10gPT0gMCAmJiBjbnQgIT0gMCkgewoJCQkJCXAgKz0gY250IC0gMTsKCQkJCQljbnQgPSAwOwoJCQkJfQoJCQkJaWYgKGFycltra10gIT0gMCkKCQkJCQljbnQrKzsKCQkJfQoJCQlwICs9IGFycltsWzBdXTsKCQkJaWYgKGkgIT0gMCkgewoJCQkJaWYgKGxbaSAtIDFdICsgdyArIDEgPT0gbFtpXSkgewoJCQkJCV90bXAgKz0gaFtpIC0gMV0gLSAxICsgaFtpXTsKCQkJCQljaGVjay5wdXNoX2JhY2sobFtpIC0gMV0gKyB3KTsKCQkJCQljaGVjazIgPSAxOwoJCQkJfQoJCQl9CgkJCWludCBpaWkgPSAwOwoJCQlmb3IgKGludCBrayA9IGxbMF07IGtrIDw9IHh4ICsgMTsga2srKykgewoJCQkJaWYgKGNoZWNrMiAmJiBpaWkgPCBjaGVjay5zaXplKCkpIHsKCQkJCQlpZiAoY2hlY2tbaWlpXSA9PSBraykgewoJCQkJCQlpaWkrKzsKCQkJCQkJY29udGludWU7CgkJCQkJfQoJCQkJfQoJCQkJaWYgKGFycltra10gIT0gYXJyW2trICsgMV0pIHsKCQkJCQlpbnQgdG1wID0gYXJyW2trICsgMV0gLSBhcnJba2tdOwoJCQkJCXAgKz0gYWJzKHRtcCk7CgkJCQkJaWYgKGFycltrayArIDFdICE9IDAgJiYgdG1wIDwgMCkKCQkJCQkJcCsrOwoJCQkJCWVsc2UgaWYgKGFycltra10gIT0gMCAmJiB0bXAgPiAwKQoJCQkJCQlwKys7CgkJCQl9CgkJCQllbHNlIGlmIChhcnJba2tdICE9IDApCgkJCQkJcCsrOwoJCQl9CgkJCV90bXAgJT0gTU9EOwoJCQlwICs9IF90bXA7CgkJCXAgJT0gTU9EOwoJCQlhbnMgKj0gcDsKCQkJYW5zICU9IE1PRDsKCQl9CgkJYW5zID0gKGFucyArIE1PRCkgJSBNT0Q7CgkJY291dCA8PCAiQ2FzZSAjIiA8PCB0c3QgKyAxIDw8ICI6ICIgPDwgYW5zIDw8ICdcbic7Cgl9Cn0=
OAoyIDIgMgoxIDIKMCAwIDAgMTAwCjMgMwowIDAgMCAxMDAKMiAyIDIKMTAgMjAKMCAwIDAgMTAwCjMgMwowIDAgMCAxMDAKNSA1IDMKMiA0IDUgOSAxMgowIDAgMCAxMDAKNCAzIDYgMyAyCjAgMCAwIDEwMAoxMCAzIDgKOSAxNCAxNQowIDEgMyA1MwoxMiA3IDE2CjUgMiAxIDM4CjUwIDEwIDE3CjQgOSAxMCAyNiAyOCA1OSA5NyAxMDAgMTA1IDEwNgoxIDAgNyA4MzIKMTMwIDEyIDgyIDQ4NyAxMiAzMCAyMTQgMTA0IDEwNCA1MjcKMjEgODEgNDEwIDYwNQoyMDAgNTIgMTgKNTI0IDU0NiA1NzYgNjAxIDYxMSA2MzEgNjUyIDY2MSA2OTQgNzE5IDcyMiA3MzIgNzYzIDc3MCA3ODUgNzg5IDc5MCA3OTYgODI3IDgyOSA4NTEgODY5IDg4MCA4OTggOTEyIDkzNiA5NDAgOTQ0IDk3MCA5OTMgMTAwOSAxMDI1IDEwMjkgMTAzMyAxMDQ4IDEwODIgMTA5NCAxMTAzIDExMjkgMTE1OCAxMTY5IDExODYgMTIwMyAxMjMxIDEyNTIgMTI4MyAxMjg3IDEzMTkgMTM0NyAxMzQ5IDEzODMgMTQxNAowIDEgMTYgNDE5NDgKMjQyMTQgNTQ5OCA5MTY2IDczNjggMzQwIDI3OCA2NTEgMzE4OCA3MzAgNDY2NSAyMzg0IDczMiA2MDk3IDE4MzEgNDQyMCA5MDM3IDc3MiA4MTUxIDUxNSA4MiA0NDI0IDExMyA2MDIzIDQyNyA2MTQgNDMxIDE1NSAyODYgNzAyIDEwMTUgMjQ1MSAzNTIgNjA0IDkwMjYgMTMzMzkgMjQxMzQgOTYwIDU1OCAxOTQgMjc5NyA0NDYwIDYyOSAyODYxIDY0NCA3Mzk2IDk2MSA0MDcgNTMzIDY2MjggMTY2IDU1OSAyMzQ0CjEyODI3Nzc5MyAyODEwODg2MDQgMzU0MjgwNzQwIDI2NzQ3CjEwMDAgOTUgMQo2ODg3IDY4ODggNjg5MCA2ODkyIDY4OTQgNjg5NiA2ODk3IDY4OTkgNjkwMSA2OTAyIDY5MDQgNjkwNiA2OTA3IDY5MDggNjkxMCA2OTEyIDY5MTMgNjkxNCA2OTE2IDY5MTcgNjkxOSA2OTIwIDY5MjIgNjkyMyA2OTI1IDY5MjcgNjkyOSA2OTMxIDY5MzMgNjkzNCA2OTM1IDY5MzcgNjkzOSA2OTQxIDY5NDMgNjk0NCA2OTQ2IDY5NDggNjk1MCA2OTUyIDY5NTQgNjk1NiA2OTU3IDY5NTkgNjk2MCA2OTYyIDY5NjQgNjk2NSA2OTY3IDY5NjggNjk3MCA2OTcxIDY5NzMgNjk3NCA2OTc1IDY5NzcgNjk3OCA2OTc5IDY5ODEgNjk4MyA2OTg1IDY5ODYgNjk4OCA2OTkwIDY5OTIgNjk5MyA2OTk1IDY5OTcgNjk5OSA3MDAwIDcwMDIgNzAwNCA3MDA1IDcwMDYgNzAwOCA3MDA5IDcwMTAgNzAxMSA3MDEzIDcwMTQgNzAxNiA3MDE3IDcwMTkgNzAyMCA3MDIxIDcwMjIgNzAyMyA3MDI1IDcwMjcgNzAyOCA3MDI5IDcwMzEgNzAzMiA3MDM0IDcwMzYKMCAxIDEgMTY0Njk2NDUwCjc5MTM3NyAxNzE0NjMgMTkxODQ0IDY4MzExNiAzOTAwNjkgMjkwMDIwIDM0NjQ1MiAyMjczODUgNDI3MTA5IDk1NTU1MCA2Mjc0OTEgNTU3MDIgODc3NTgxIDcxOTUxNiAzODY3NjUgNzgzNjk0IDc1MTQ0MSA5OTM1MzMgNjc3OTI5IDkzMDk4MiA0NzM1MDIgNjk4NDMzIDg2MjIzIDQ0MjM5MCA2ODYxNzIgMjc1NDMgNzQ2NTE2IDQzNTU2IDkxOTQyNCA0NTQyNzUgNTkwMTkzIDY1MDU1IDU2NjkwOSA1Mzk4MTkgOTY0NjEwIDczMDQ4NiA2NjU2OTAgNTI0NjcxIDM3NDU3MCAyNjcwNTkgNjg3NjQ3IDc1ODI3NSA0OTg0NTEgNzIzMDMxIDYxODY2NSA2NTc3MjMgNjI4NDk5IDkzNzgxMCAxMjQ4OTMgMjA2NzA2IDgyOTAzNCA0MDYxMTEgMTI0NDA5IDMwMjA1NCAyNTgyMTYgMTYyNDI2IDYyMzMwMiA3NjM5MjMgNjM4ODI4IDk2MTE1MSA4NzUwNTAgOTA2Nzc4IDU5MTc1MCA4NTU5MDQgNTg1MzA2IDY1NTE4MiAyNDQxNTggNDA4MzUgMzE4MjUyIDM2NDEyNCA3MjUzNTggNTA2ODA2IDQyMzQ5OCA1NTMxMDggODAwMjY2IDY2OTk2OCA5MDU0MTAgNzYxNDk2IDcxODU5MiA4MDYzNzMgNDg5NTMxIDk2MDU0NCAyMzUzMjIgMTk4ODIxIDYyNjA1MSA1ODU0NDcgMzQ1NDczIDU1MDU3IDc4MzIzNSA2MzIwNTMgMzA2NzQ3IDQ1ODk3MSA1Njg5ODAgMjgyNjM0IDUzMTAyOQo1MjYxNTY5NTIgNDAzMDIwNTcgODUzMjYzNjUxIDE5NDExNjczMQoyMDAwMDAgMiAyMAoxIDMKMCAxIDEwMCA1MDAwMDAwMDAKMTAwMDAwMDAwIDMwMDAwMDAwMAowIDEgMTAwIDUwMDAwMDAwMAo=
8
2 2 2
1 2
0 0 0 100
3 3
0 0 0 100
2 2 2
10 20
0 0 0 100
3 3
0 0 0 100
5 5 3
2 4 5 9 12
0 0 0 100
4 3 6 3 2
0 0 0 100
10 3 8
9 14 15
0 1 3 53
12 7 16
5 2 1 38
50 10 17
4 9 10 26 28 59 97 100 105 106
1 0 7 832
130 12 82 487 12 30 214 104 104 527
21 81 410 605
200 52 18
524 546 576 601 611 631 652 661 694 719 722 732 763 770 785 789 790 796 827 829 851 869 880 898 912 936 940 944 970 993 1009 1025 1029 1033 1048 1082 1094 1103 1129 1158 1169 1186 1203 1231 1252 1283 1287 1319 1347 1349 1383 1414
0 1 16 41948
24214 5498 9166 7368 340 278 651 3188 730 4665 2384 732 6097 1831 4420 9037 772 8151 515 82 4424 113 6023 427 614 431 155 286 702 1015 2451 352 604 9026 13339 24134 960 558 194 2797 4460 629 2861 644 7396 961 407 533 6628 166 559 2344
128277793 281088604 354280740 26747
1000 95 1
6887 6888 6890 6892 6894 6896 6897 6899 6901 6902 6904 6906 6907 6908 6910 6912 6913 6914 6916 6917 6919 6920 6922 6923 6925 6927 6929 6931 6933 6934 6935 6937 6939 6941 6943 6944 6946 6948 6950 6952 6954 6956 6957 6959 6960 6962 6964 6965 6967 6968 6970 6971 6973 6974 6975 6977 6978 6979 6981 6983 6985 6986 6988 6990 6992 6993 6995 6997 6999 7000 7002 7004 7005 7006 7008 7009 7010 7011 7013 7014 7016 7017 7019 7020 7021 7022 7023 7025 7027 7028 7029 7031 7032 7034 7036
0 1 1 164696450
791377 171463 191844 683116 390069 290020 346452 227385 427109 955550 627491 55702 877581 719516 386765 783694 751441 993533 677929 930982 473502 698433 86223 442390 686172 27543 746516 43556 919424 454275 590193 65055 566909 539819 964610 730486 665690 524671 374570 267059 687647 758275 498451 723031 618665 657723 628499 937810 124893 206706 829034 406111 124409 302054 258216 162426 623302 763923 638828 961151 875050 906778 591750 855904 585306 655182 244158 40835 318252 364124 725358 506806 423498 553108 800266 669968 905410 761496 718592 806373 489531 960544 235322 198821 626051 585447 345473 55057 783235 632053 306747 458971 568980 282634 531029
526156952 40302057 853263651 194116731
200000 2 20
1 3
0 1 100 500000000
100000000 300000000
0 1 100 500000000