CDQ分治+FFT，O(klog^2k)。

#include <cstdio>
#include <cmath>
#include <algorithm>
#define V_MAX 2
#define C_MAX 3
#define Q_MAX 20
#define N_MAX 100000
#define L_MAX 131072
#define R_MAX 17
typedef unsigned long long lnt;
typedef unsigned unt;
typedef void vnt;
typedef double dec;
const unt P = 47;
const dec tau = std::acos(dec(-1)) * 2;
inline unt mod(unt a) { return a % P; }
inline unt moc(unt a) { return a < P ? a : a - P; }
inline vnt upd(unt & a, unt b) { a = mod(a + b); }
inline vnt upc(unt & a, unt b) { a = moc(a + b); }
struct vec
{
    dec x, y;
    vec operator + (const vec & z) const { return (vec) {x + z.x, y + z.y}; }
    vec operator - (const vec & z) const { return (vec) {x - z.x, y - z.y}; }
    vec operator * (const vec & z) const { return (vec) {x * z.x - y * z.y, x * z.y + y * z.x}; }
    friend vec operator * (unt w, const vec & z) { return (vec) {w * z.x, w * z.y}; }
} vec_0, vec_1 = (vec) {1, 0}, w[R_MAX];
int L, R, rev[L_MAX + 1];
inline vnt fft(vec a[])
{
    int i, j, k, r = R; vec x, u, v;
    for (i = 1; i < L; ++i)
        if (i < rev[i])
            std::swap(a[i], a[rev[i]]);
    for (k = 1, --r; k < L; k <<= 1, --r)
        for (i = 0; i < L; i += k << 1)
            for (j = 0, x = vec_1; j < k; ++j, x = x * w[r])
                u = a[i + j], v = x * a[i + j + k], a[i + j] = u + v, a[i + j + k] = u - v;
}
int V, d[V_MAX][C_MAX];
unt e[V_MAX][C_MAX], f[V_MAX][V_MAX][N_MAX + 1];
vec a[V_MAX][V_MAX][L_MAX + 1], b[V_MAX][V_MAX][L_MAX + 1], c[V_MAX][V_MAX][L_MAX + 1];
inline vnt sol(int l, int r)
{
    if (r - l == 1)
    {
        if (l == 0)
            for (int x = 0; x < V; ++x)
                f[x][x][0] = 1;
        for (int x = 0; x < V; ++x)
            for (int y = 0; y < V; ++y)
                upd(f[x][y][l + 1], e[x][2] * f[d[x][2]][y][l]);
    }
    else
    {
        int m = l + ((r - l) >> 1);
        sol(l, m);
        if (l == 0)
        {
            for (L = 1, R = 0; L < (m - l) * 2 - 1; L <<= 1, ++R);
            for (int i = 1; i < L; ++i)
                rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (R - 1));
            w[0] = (vec) {std::cos(tau / L), std::sin(tau / L)};
            for (int i = 0; i < R - 1; ++i)
                w[i + 1] = w[i] * w[i];
            for (int x = 0; x < V; ++x)
                for (int y = 0; y < V; ++y)
                {
                    for (int i = 0; i < m; ++i)
                        a[x][y][i].x = f[x][y][i], a[x][y][i].y = 0;
                    for (int i = m; i < L; ++i)
                        a[x][y][i] = vec_0;
                    fft(a[x][y]);
                }
            for (int x = 0; x < V; ++x)
                for (int y = 0; y < V; ++y)
                    for (int z = 0; z < V; ++z)
                        for (int i = 0; i < L; ++i)
                            c[x][z][i] = c[x][z][i] + mod(e[x][0] * e[y][1]) * a[d[x][0]][y][i] * a[d[y][1]][z][i];
        }
        else
        {
            for (L = 1, R = 0; L < m - l + r - l - 2; L <<= 1, ++R);
            for (int i = 1; i < L; ++i)
                rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (R - 1));
            w[0] = (vec) {std::cos(tau / L), std::sin(tau / L)};
            for (int i = 0; i < R - 1; ++i)
                w[i + 1] = w[i] * w[i];
            for (int x = 0; x < V; ++x)
                for (int y = 0; y < V; ++y)
                {
                    for (int i = l; i < m; ++i)
                        a[x][y][i - l].x = f[x][y][i], a[x][y][i - l].y = 0;
                    for (int i = m - l; i < L; ++i)
                        a[x][y][i] = vec_0;
                    fft(a[x][y]);
                }
            for (int x = 0; x < V; ++x)
                for (int y = 0; y < V; ++y)
                {
                    for (int i = 0; i < r - l - 1; ++i)
                        b[x][y][i].x = f[x][y][i], b[x][y][i].y = 0;
                    for (int i = r - l - 1; i < L; ++i)
                        b[x][y][i] = vec_0;
                    fft(b[x][y]);
                }
            for (int x = 0; x < V; ++x)
                for (int y = 0; y < V; ++y)
                    for (int z = 0; z < V; ++z)
                        for (int i = 0; i < L; ++i)
                            c[x][z][i] = c[x][z][i] + mod(e[x][0] * e[y][1]) * (a[d[x][0]][y][i] * b[d[y][1]][z][i] + b[d[x][0]][y][i] * a[d[y][1]][z][i]);
        }
        w[0].y = -w[0].y;
        for (int i = 0; i < R - 1; ++i)
            w[i + 1] = w[i] * w[i];
        for (int u = 0; u < V; ++u)
            for (int v = 0; v < V; ++v)
            {
                fft(c[u][v]);
                for (int i = m + 1; i < r + 1; ++i)
                    upd(f[u][v][i], unt(lnt(c[u][v][i - l - 2].x / L + 0.5) % P));
                for (int i = 0; i < L; ++i)
                    c[u][v][i] = vec_0;
            }
        sol(m, r);
    }
}
int Q, N;
struct qry { int s, t, n; } q[Q_MAX];
int main()
{
    scanf("%d", &V);
    for (int x = 0; x < V; ++x)
        for (int k = 0; k < C_MAX; ++k)
            scanf("%d %u", &d[x][k], &e[x][k]), e[x][k] %= P;
    scanf("%d", &Q);
    for (int k = 0; k < Q; ++k)
        scanf("%d %d %d", &q[k].s, &q[k].t, &q[k].n), N = std::max(N, q[k].n);
    sol(0, N);
    for (int k = 0; k < Q; ++k)
        printf("%u\n", f[q[k].s][q[k].t][q[k].n]);
    return 0;
}

虽然我没有AC但我来抢个沙发