# bzoj 1898 [Zjoi2005]Swamp 沼泽鳄鱼

6 8 1 5 3

0 2

2 1

1 0

0 5

5 1

1 4

4 3

3 5

1

3 0 5 1

2

【样例说明】

### 题解

#include <cstdio>
#include <cstring>
using namespace std;
int mn;
long long p;
const int mod = 10000;
#define MN 55
#define N 3010
struct matrixs {
int m[MN][MN];
void clear() { memset(m, 0, sizeof m); }
matrixs operator * (const matrixs &a) const {
matrixs ans = {};
for (int i = 1; i <= mn; i++)
for (int k = 1; k <= mn; k++)
if (m[i][k])
for (int j = 1; j <= mn; j++)
ans.m[i][j] = (ans.m[i][j] + (long long)m[i][k] * a.m[k][j]) % mod;
return ans;
}
matrixs matrix_pow(long long p) {
matrixs ans,a = (*this);
ans.clear();
for (int i = 1; i <= mn; i++) ans.m[i][i] = 1;
for (; p; a = a * a, p >>= 1)
if (p & 1) ans = ans * a;
return ans;
}
void print() {
for (int i = 1; i <= mn; ++i, puts(""))
for (int j = 1; j <= mn; ++j)
printf("%d ", m[i][j]);
}
}m[14];
struct edge {
int fr, to;
}e[N];
int n, ms, st, ed, nf, x, fi[N], can[MN][MN];
long long k;
main() {
scanf("%d%d%d%d%lld", &n, &ms, &st, &ed, &k);
st++, ed++, mn = n;
for (int i = 1; i <= ms; ++i)
scanf("%d%d", &e[i].fr, &e[i].to),
e[i].fr++, e[i].to++;
scanf("%d", &nf);
while (nf--) {
scanf("%d", &x);
for (int i = 0; i < x; ++i)
scanf("%d", &fi[i]), fi[i]++;
for (int i = 0; i < 12; ++i)
can[i][fi[i % x]] = 1;
}
for (int i = 1; i <= n; ++i) can[12][i] = can[0][i];
for (int i = 1; i <= n; ++i) m[0].m[i][i] = 1;
for (int i = 1; i <= 12; ++i) {
for (int j = 1; j <= ms; ++j) {
if (!can[i - 1][e[j].fr] && !can[i][e[j].to])
m[i].m[e[j].fr][e[j].to]++;
if (!can[i - 1][e[j].to] && !can[i][e[j].fr])
m[i].m[e[j].to][e[j].fr]++;
}
m[0] = m[0] * m[i];
//      m[0].print(); puts("");
}
m[0] = m[0].matrix_pow(k / 12);
//  m[0].print(); puts("");
for (int i = 1; i <= k % 12; ++i)
m[0] = m[0] * m[i]/*, m[0].print(); puts("")*/;
printf("%d\n", m[0].m[st][ed]);
}