各頂点に対してそこに存在する正電荷・負電荷の量がどのように遷移するかの行列を考えると、これは何ステップ目かに依存しません。そのような \(2N\times 2N\) 行列を作り、\(T\) 乗した行列を求めれば良いです。

実装例(Python3)

import sys

input = sys.stdin.readline
MOD = 1000000007


def mat_mul(a, b):
    n = len(a)
    c = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if a[i][k]:
                for j in range(n):
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD
    return c


def mat_pow(a, k):
    n = len(a)
    b = [[int(i == j) for j in range(n)] for i in range(n)]
    while k:
        if k & 1:
            b = mat_mul(b, a)
        a = mat_mul(a, a)
        k >>= 1
    return b


n, m, t = map(int, input().split())
s, g = map(int, input().split())
r = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    inv = pow(sum(r[i]), MOD - 2, MOD)
    for j in range(n):
        r[i][j] = r[i][j] * inv % MOD
inv = [[False] * n for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    inv[u][v] = True
d = [[0] * (2 * n) for _ in range(2 * n)]
for u in range(n):
    for v in range(n):
        if inv[u][v]:
            d[u][v + n] = d[u + n][v] = r[u][v]
        else:
            d[u][v] = d[u + n][v + n] = r[u][v]
d = mat_pow(d, t)
print(d[s - 1][g - 1])