@staticmethod
def c():
    (n, a, b, m, *xy) = map(int, sys.stdin.read().split())
    (x, y) = (np.array(xy).reshape(m, 2).T - 1)
    a -= 1
    b -= 1
    g = csgraph_to_dense(csr_matrix((np.ones(m), (x, y)), (n, n), dtype=np.int8))
    g = np.logical_or(g, g.T)
    paths = np.zeros(n, dtype=np.int64).reshape((- 1), 1)
    paths[(a, 0)] = 1
    while (not paths[(b, 0)]):
        paths = (np.dot(g, paths) % MOD)
    print(paths[(b, 0)])
@staticmethod
def c():
    (n, a, b, m, *xy) = map(int, sys.stdin.read().split())
    (x, y) = (np.array(xy).reshape(m, 2).T - 1)
    a -= 1
    b -= 1
    g = csgraph_to_dense(csr_matrix((np.ones(m), (x, y)), (n, n), dtype=np.int8))
    g = np.logical_or(g, g.T)
    paths = np.zeros(n, dtype=np.int64).reshape((- 1), 1)
    paths[(a, 0)] = 1
    while (not paths[(b, 0)]):
        paths = (np.dot(g, paths) % MOD)
    print(paths[(b, 0)])