from copy import deepcopy
from random import randint
from math import pi, sin, cos
from __pypy__.builders import StringBuilder
import sys
from os import read as os_read, write as os_write
from atexit import register as atexist_register
from typing import Generic, Iterator, List, Tuple, Dict, Iterable, Sequence, Callable, Union, Optional, TypeVar
T = TypeVar('T')
Graph = List[List[int]]
Poly = List[int]
Vector = List[int]
Matrix = List[List[int]]
Func10 = Callable[[int], None]
Func20 = Callable[[int, int], None]
Func11 = Callable[[int], int]
Func21 = Callable[[int, int], int]
Func31 = Callable[[int, int, int], int]

class Fastio:
    ibuf = bytes()
    pil = pir = 0
    sb = StringBuilder()
    def load(self):
        self.ibuf = self.ibuf[self.pil:]
        self.ibuf += os_read(0, 131072)
        self.pil = 0; self.pir = len(self.ibuf)
    def flush_atexit(self): os_write(1, self.sb.build().encode())
    def flush(self):
        os_write(1, self.sb.build().encode())
        self.sb = StringBuilder()
    def fastin(self):
        if self.pir - self.pil < 64: self.load()
        minus = x = 0
        while self.ibuf[self.pil] < 45: self.pil += 1
        if self.ibuf[self.pil] == 45: minus = 1; self.pil += 1
        while self.ibuf[self.pil] >= 48:
            x = x * 10 + (self.ibuf[self.pil] & 15)
            self.pil += 1
        if minus: return -x
        return x
    def fastin_string(self):
        if self.pir - self.pil < 64: self.load()
        while self.ibuf[self.pil] <= 32: self.pil += 1
        res = bytearray()
        while self.ibuf[self.pil] > 32:
            if self.pir - self.pil < 64: self.load()
            res.append(self.ibuf[self.pil])
            self.pil += 1
        return res
    def fastout(self, x): self.sb.append(str(x))
    def fastoutln(self, x): self.sb.append(str(x)); self.sb.append('\n')
fastio = Fastio()
rd = fastio.fastin; rds = fastio.fastin_string; wt = fastio.fastout; wtn = fastio.fastoutln; flush = fastio.flush
atexist_register(fastio.flush_atexit)
sys.stdin = None; sys.stdout = None
def rdl(n): return [rd() for _ in range(n)]
def wtnl(l): wtn(' '.join(map(str, l)))
def wtn_yes(): wtn("Yes")
def wtn_no(): wtn("No")

# https://judge.yosupo.jp/submission/46633
# cooley_tukey ?
# maybe https://nyaannyaan.github.io/library/ntt/complex-fft.hpp
class CooleyTukey:
    isbuilt = 0
    def __init__(self, k: int=20) -> None:
        self.wr = [0] * (1 << 20)
        self.wi = [0] * (1 << 20)
        self.baser = [0] * 20
        self.basei = [0] * 20
        self.setw(k)
        self.isbuilt = 1

    @staticmethod
    def mul(xr: float, xi: float, yr: float, yi: float) -> tuple:
        return xr * yr - xi * yi, xr * yi + yr * xi

    def genw(self, i: int, b: int, zr: float, zi: float) -> None:
        if b == -1:
            self.wr[i] = zr
            self.wi[i] = zi
        else:
            self.genw(i, b - 1, zr, zi)
            wr, wi = self.baser[b], self.basei[b]
            self.genw(i | (1 << b), b - 1, zr * wr - zi * wi, zr * wi + zi * wr)

    def setw(self, k: int) -> None:
        k -= 1
        arg = pi / (1 << k)
        i = 0
        j = 1 << (k - 1)
        while j:
            self.baser[i] = cos(arg * j)
            self.basei[i] = sin(arg * j)
            i += 1
            j >>= 1
        self.genw(0, k - 1, 1, 0)

    def fft(self, ar: List[float], ai: List[float], k: int) -> None:
        if k == 0: return
        if k == 1:
            ar[0], ar[1] = ar[0] + ar[1], ar[0] - ar[1]
            ai[0], ai[1] = ai[0] + ai[1], ai[0] - ai[1]
            return
        if k & 1:
            v = 1 << (k - 1)
            for j in range(v):
                ar[j], ar[j + v] = ar[j] + ar[j + v], ar[j] - ar[j + v]
                ai[j], ai[j + v] = ai[j] + ai[j + v], ai[j] - ai[j + v]
        u = 1 << (k & 1)
        v = 1 << (k - 2 - (k & 1))
        wr1, wi1 = self.wr[1], self.wi[1]
        while v:
            for j0 in range(v):
                t0r = ar[j0]; t0i = ai[j0]
                t1r = ar[j0 + v]; t1i = ai[j0 + v]
                t2r = ar[j0 + v * 2]; t2i = ai[j0 + v * 2]
                t3r = ar[j0 + v * 3]; t3i = ai[j0 + v * 3]
                t1m3r, t1m3i = self.mul(t1r - t3r, t1i - t3i, wr1, wi1)
                ar[j0] = (t0r + t2r) + (t1r + t3r); ai[j0] = (t0i + t2i) + (t1i + t3i)
                ar[j0 + v] = (t0r + t2r) - (t1r + t3r); ai[j0 + v] = (t0i + t2i) - (t1i + t3i)
                ar[j0 + v * 2] = (t0r - t2r) + t1m3r; ai[j0 + v * 2] = (t0i - t2i) + t1m3i
                ar[j0 + v * 3] = (t0r - t2r) - t1m3r; ai[j0 + v * 3] = (t0i - t2i) - t1m3i

            for jh in range(1, u):
                p = jh * v * 4
                Wr = self.wr[jh]; Wi = self.wi[jh]
                Xr = self.wr[jh << 1]; Xi = self.wi[jh << 1]
                WXr, WXi = self.mul(Wr, Wi, Xr, Xi)
                for offset in range(v):
                    t0r = ar[p + offset]; t0i = ai[p + offset]
                    t1r, t1i = self.mul(ar[p + offset + v], ai[p + offset + v], Xr, Xi)
                    t2r, t2i = self.mul(ar[p + offset + v * 2], ai[p + offset + v * 2], Wr, Wi)
                    t3r, t3i = self.mul(ar[p + offset + v * 3], ai[p + offset + v * 3], WXr, WXi)
                    t1m3r, t1m3i = self.mul(t1r - t3r, t1i - t3i, wr1, wi1)
                    ar[p + offset] = (t0r + t2r) + (t1r + t3r); ai[p + offset] = (t0i + t2i) + (t1i + t3i)
                    ar[p + offset + v] = (t0r + t2r) - (t1r + t3r); ai[p + offset + v] = (t0i + t2i) - (t1i + t3i)
                    ar[p + offset + v * 2] = (t0r - t2r) + t1m3r; ai[p + offset + v * 2] = (t0i - t2i) + t1m3i
                    ar[p + offset + v * 3] = (t0r - t2r) - t1m3r; ai[p + offset + v * 3] = (t0i - t2i) - t1m3i
            u <<= 2
            v >>= 2

    def ifft(self, ar: List[float], ai: List[float], k: int) -> None:
        if k == 0: return
        if k == 1:
            ar[0], ar[1] = ar[0] + ar[1], ar[0] - ar[1]
            ai[0], ai[1] = ai[0] + ai[1], ai[0] - ai[1]
            return
        u = 1 << (k - 2)
        v = 1
        wr1, mwi1 = self.wr[1], -self.wi[1]
        while u:
            for j0 in range(v):
                t0r = ar[j0]; t0i = ai[j0]
                t1r = ar[j0 + v]; t1i = ai[j0 + v]
                t2r = ar[j0 + v * 2]; t2i = ai[j0 + v * 2]
                t3r = ar[j0 + v * 3]; t3i = ai[j0 + v * 3]
                t2m3r, t2m3i = self.mul(t2r - t3r, t2i - t3i, wr1, mwi1)
                ar[j0] = (t0r + t1r) + (t2r + t3r); ai[j0] = (t0i + t1i) + (t2i + t3i)
                ar[j0 + v * 2] = (t0r + t1r) - (t2r + t3r); ai[j0 + v * 2] = (t0i + t1i) - (t2i + t3i)
                ar[j0 + v] = (t0r - t1r) + t2m3r; ai[j0 + v] = (t0i - t1i) + t2m3i
                ar[j0 + v * 3] = (t0r - t1r) - t2m3r; ai[j0 + v * 3] = (t0i - t1i) - t2m3i
            for jh in range(1, u):
                p = jh * v * 4
                Wr = self.wr[jh]; Wi = -self.wi[jh]
                Xr = self.wr[(jh << 1) + 0]; Xi = -self.wi[(jh << 1) + 0]
                Yr = self.wr[(jh << 1) + 1]; Yi = -self.wi[(jh << 1) + 1]
                for offset in range(v):
                    t0r = ar[p + offset]; t0i = ai[p + offset]
                    t1r = ar[p + offset + v]; t1i = ai[p + offset + v]
                    t2r = ar[p + offset + v * 2]; t2i = ai[p + offset + v * 2]
                    t3r = ar[p + offset + v * 3]; t3i = ai[p + offset + v * 3]
                    t0m1r, t0m1i = self.mul(t0r - t1r, t0i - t1i, Xr, Xi)
                    t2m3r, t2m3i = self.mul(t2r - t3r, t2i - t3i, Yr, Yi)
                    ar[p + offset] = (t0r + t1r) + (t2r + t3r); ai[p + offset] = (t0i + t1i) + (t2i + t3i)
                    ar[p + offset + v] = t0m1r + t2m3r; ai[p + offset + v] = t0m1i + t2m3i
                    ar[p + offset + v * 2], ai[p + offset + v * 2] = self.mul((t0r + t1r) - (t2r + t3r), (t0i + t1i) - (t2i + t3i), Wr, Wi)
                    ar[p + offset + v * 3], ai[p + offset + v * 3] = self.mul(t0m1r - t2m3r, t0m1i - t2m3i, Wr, Wi)
            u >>= 2
            v <<= 2
        if k & 1:
            u = 1 << (k - 1)
            for j in range(u):
                ar[j], ar[j + u] = ar[j] + ar[j + u], ar[j] - ar[j + u]
                ai[j], ai[j + u] = ai[j] + ai[j + u], ai[j] - ai[j + u]

    def fft_real(self, ALr: List[float], ALi: List[float], AHr: List[float], AHi: List[float], k: int) -> None:
        self.fft(ALr, ALi, k)
        AHr[0] = ALi[0] * 2; AHi[0] = 0
        ALr[0] = ALr[0] * 2; ALi[0] = 0
        AHr[1] = ALi[1] * 2; AHi[1] = 0
        ALr[1] = ALr[1] * 2; ALi[1] = 0
        i = 2; y = 2
        while y < 1 << k:
            while i < y << 1:
                j = i ^ (y - 1)
                AHr[i] = ALi[j] + ALi[i]; AHi[i] = ALr[j] - ALr[i]
                ALr[i] = ALr[j] + ALr[i]; ALi[i] = -ALi[j] + ALi[i]
                AHr[j] = AHr[i]; AHi[j] = -AHi[i]
                ALr[j] = ALr[i]; ALi[j] = -ALi[i]
                i += 2
            y <<= 1

    def karatsuba(self, a: Vector, b: Vector, mod: int) -> Vector:
        B = 32000
        bbmod = B * B % mod
        l = len(a) + len(b) - 1
        k = max(2, l.bit_length())
        M = 1 << k
        if not self.isbuilt: self.setw(k)

        alr = [float()] * M
        ali = [float()] * M
        ahr = [float()] * M
        ahi = [float()] * M
        for i, x in enumerate(a):
            quo, rem = divmod(x, B)
            alr[i], ali[i] = float(rem), float(quo)
        self.fft_real(alr, ali, ahr, ahi, k)

        blr = [float()] * M
        bli = [float()] * M
        bhi = [float()] * M
        bhr = [float()] * M
        for i, x in enumerate(b):
            quo, rem = divmod(x, B)
            blr[i], bli[i] = float(rem), float(quo)
        self.fft_real(blr, bli, bhr, bhi, k)

        for i in range(M):
            alri = alr[i]; alii = ali[i]
            mahii = -ahi[i]; ahri = ahr[i]
            tmp1r, tmp1i = self.mul(alri, alii, blr[i], bli[i])
            tmp2r, tmp2i = self.mul(mahii, ahri, bhr[i], bhi[i])
            tmp3r, tmp3i = self.mul(alri, alii, bhr[i], bhi[i])
            tmp4r, tmp4i = self.mul(mahii, ahri, blr[i], bli[i])
            blr[i] = tmp1r + tmp2r; bli[i] = tmp1i + tmp2i
            bhr[i] = tmp3r + tmp4r; bhi[i] = tmp3i + tmp4i

        self.ifft(blr, bli, k)
        self.ifft(bhr, bhi, k)

        u = [0] * l
        im = float(1 / (4 * M))
        for i in range(l):
            x1 = round(blr[i] * im) % mod
            x2 = (round(bhr[i] * im) + round(bhi[i] * im)) % mod * B % mod
            x3 = round(bli[i] * im) % mod * bbmod % mod
            x = x1 + x2 + x3
            if x >= mod: x -= mod
            if x >= mod: x -= mod
            u[i] = x
        return u

    def karatsuba_pow2(self, a: Vector, mod: int) -> Vector:
        B = 32000
        l = len(a) * 2 - 1
        k = 2; M = 4
        while M < l:
            M <<= 1
            k += 1
        self.setw(k)
        alr = [float()] * M
        ali = [float()] * M
        ahr = [float()] * M
        ahi = [float()] * M
        for i, x in enumerate(a):
            quo, rem = divmod(x, B)
            alr[i], ali[i] = float(rem), float(quo)

        self.fft_real(alr, ali, ahr, ahi, k)

        for i in range(M):
            tmp1r = alr[i]; tmp1i = ali[i]
            tmp2r = -ahi[i]; tmp2i = ahr[i]
            tmp3r = tmp1r; tmp3i = tmp1i
            tmp4r = tmp2r; tmp4i = tmp2i
            tmp1r, tmp1i = self.mul(tmp1r, tmp1i, alr[i], ali[i])
            tmp2r, tmp2i = self.mul(tmp2r, tmp2i, ahr[i], ahi[i])
            tmp3r, tmp3i = self.mul(tmp3r, tmp3i, ahr[i], ahi[i])
            tmp4r, tmp4i = self.mul(tmp4r, tmp4i, alr[i], ali[i])
            alr[i] = tmp1r + tmp2r; ali[i] = tmp1i + tmp2i
            ahr[i] = tmp3r + tmp4r; ahi[i] = tmp3i + tmp4i

        self.ifft(alr, ali, k)
        self.ifft(ahr, ahi, k)

        u = [0] * l
        im = float(1 / (4 * M))
        for i in range(l):
            alr[i] *= im; ali[i] *= im
            ahr[i] *= im; ahi[i] *= im
            x1 = round(alr[i]) % mod
            x2 = (round(ahr[i]) + round(ahi[i])) % mod * B % mod
            x3 = round(ali[i]) % mod * (B * B % mod) % mod
            x1 += x2
            if x1 >= mod: x1 -= mod
            x1 += x3
            if x1 >= mod: x1 -= mod
            u[i] = x1
        return u

def modinv(a: int, m: int) -> int:
    '''return x s.t. x == a^(-1) (mod m)'''
    b = m; u = 1; v = 0
    while b:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    u %= m
    return u

# https://nyaannyaan.github.io/library/fps/berlekamp-massey.hpp
def berlekamp_massey(s: Vector, mod: int) -> Vector:
    N = len(s)
    b = [1]
    c = [1]
    y = 1
    for ed in range(1, N + 1):
        l = len(c)
        m = len(b)
        x = 0
        for i, a in enumerate(c): x += a * s[ed - l + i]
        x %= mod
        b.append(0)
        m += 1
        if x == 0: continue
        freq = x * modinv(y, mod) % mod
        if l < m:
            tmp = c[:]
            c[:0] = [0] * (m - l)
            for i in range(m): c[m - 1 - i] = (c[m - 1 - i] - freq * b[m - 1 - i]) % mod
            b = tmp
            y = x
        else:
            for i in range(m): c[l - 1 - i] = (c[l - 1 - i] - freq * b[m - 1 - i]) % mod
    c.reverse()
    return c

# https://nyaannyaan.github.io/library/fps/formal-power-series.hpp
class FPS:
    ntt = None
    def __init__(self, mod: int) -> None:
        self.mod = mod

    @staticmethod
    def shrink(a: Vector) -> None:
        '''remove high degree coef == 0'''
        while a and not a[-1]: a.pop()

    @staticmethod
    def resize(a: Poly, length: int, val: int=0) -> None:
        a[length:] = []
        a[len(a):] = [val] * (length - len(a))

    def add(self, l: Poly, r: Union[Poly, int]) -> Poly:
        '''l += r'''
        if type(r) is int:
            res = l[:]
            res[0] = (res[0] + r) % self.mod
            return res
        mod = self.mod
        if type(r) is list:
            if len(l) < len(r):
                res = r[::]
                for i, x in enumerate(l): res[i] += x
            else:
                res = l[::]
                for i, x in enumerate(r): res[i] += x
            return [x % mod for x in res]
        raise TypeError()

    def sub(self, l: Poly, r: Union[Poly, int]) -> Poly:
        '''l -= r'''
        if type(r) is int: return self.add(l, -r)
        if type(r) is list: return self.add(l, self.neg(r))
        raise TypeError()

    def neg(self, a: Poly) -> Poly:
        '''a *= -1'''
        mod = self.mod
        return [mod - x if x else 0 for x in a]

    def matmul(self, l: Poly, r: Poly) -> Poly:
        'not verified'
        mod = self.mod
        return [x * r[i] % mod for i, x in enumerate(l)]

    def div(self, l: Poly, r: Poly) -> Poly:
        '''return: quo s.t. l = r*quo + rem'''
        if len(l) < len(r): return []
        n = len(l) - len(r) + 1
        if len(r) > 64:
            return self.mul(l[::-1][:n], self.inv(r[::-1], n))[:n][::-1]
        mod = self.mod
        f, g = l[::], r[::]
        cnt = 0
        while g and not g[-1]:
            g.pop()
            cnt += 1
        coef = modinv(g[-1], mod)
        g = self.mul(g, coef)
        deg = len(f) - len(g) + 1
        gs = len(g)
        quo = [0] * deg
        for i in range(deg)[::-1]:
            quo[i] = x = f[i + gs - 1] % mod
            for j, y in enumerate(g):
                f[i + j] -= x * y
        return self.mul(quo, coef) + [0] * cnt

    def modulo(self, l: Poly, r: Poly) -> Poly:
        '''return: rem s.t. l = r*quo + rem'''
        res = self.sub(l, self.mul(self.div(l, r), r))
        self.shrink(res)
        return res

    def divmod(self, l: Poly, r: Poly) -> Tuple[Poly, Poly]:
        '''return: quo, rem s.t. l = r*quo + rem'''
        quo = self.div(l, r)
        rem = self.sub(l, self.mul(quo, r))
        self.shrink(rem)
        return quo, rem

    def eval(self, a: Poly, x: int) -> int:
        mod = self.mod
        r = 0; w = 1
        for v in a:
            r += w * v % mod
            w = w * x % mod
        return r % mod

    def pow(self, f: Poly, k: int, deg=-1) -> Poly:
        '''return: g s.t. g == f**k (mod x**deg)'''
        n = len(f)
        if deg == -1: deg = n
        if k == 0:
            if not deg: return []
            ret = [0] * deg
            ret[0] = 1
            return ret
        mod = self.mod
        for i, x in enumerate(f):
            if x:
                rev = modinv(x, mod)
                ret = self.mul(self.exp(self.mul(self.log(self.mul(f, rev)[i:], deg), k), deg), pow(x, k, mod))
                ret[:0] = [0] * (i * k)
                if len(ret) < deg:
                    self.resize(ret, deg)
                    return ret
                return ret[:deg]
            if (i + 1) * k >= deg: break
        return [0] * deg

    def log(self, f: Poly, deg=-1) -> Poly:
        '''return: g s.t. g == log(f) (mod x**deg)'''
        # assert(a[0] == 1)
        if deg == -1: deg = len(f)
        return self.integral(self.mul(self.diff(f), self.inv(f, deg))[:deg - 1])

    def integral(self, a: Poly) -> Poly:
        mod = self.mod
        n = len(a)
        res = [0] * (n + 1)
        if n: res[1] = 1
        for i in range(2, n + 1):
            j, k = divmod(mod, i)
            res[i] = (-res[k] * j) % mod
        for i, x in enumerate(a): res[i + 1] = res[i + 1] * x % mod
        return res

    def diff(self, f: Poly) -> Poly:
        '''return: dfdx'''
        mod = self.mod
        return [i * x % mod for i, x in enumerate(f) if i]

    def mul(self, l: list, r: Union[list, int]) -> list:
        raise AttributeError("'mul' method is virtual function. please override")

    def mul2(self, l: list) -> list:
        raise AttributeError("'mul2' method is virtual function. please override")

    def inv(self, a: list, deg: int=-1) -> list:
        raise AttributeError("'inv' method is virtual function. please override")

    def exp(self, a: list, deg: int=-1) -> list:
        raise AttributeError("'exp' method is virtual function. please override")

# arbitrary_nttだとTLEするのでCooleyTukeyを使いたい
# 2倍くらい速いっぽい
# https://nyaannyaan.github.io/library/fps/arbitrary-fps.hpp
def set_fft(self: FPS) -> None:
    self.ntt = CooleyTukey()
FPS.set_fft = set_fft

def mul(self: FPS, l: Poly, r: Union[Poly, int]) -> Poly:
    '''
    if r is int: l *= r
    if r is Polynomial: convolve l and r
    '''
    mod = self.mod
    if type(r) is int: return [x * r % mod for x in l]
    if type(r) is list:
        if not l or not r: return []
        if self.ntt is None: self.set_fft()
        return self.ntt.karatsuba(l, r, mod)
    raise TypeError()
FPS.mul = mul

def mul2(self: FPS, l: Poly) -> Poly:
    '''
    convolve l and l
    '''
    mod = self.mod
    if self.ntt is None: self.set_fft()
    return self.ntt.karatsuba_pow2(l, mod)
FPS.mul2 = mul2

def inv(self: FPS, a: Poly, deg: int=-1) -> Poly:
    '''return: g s.t. a*g == 1 (mod x**deg)'''
    # assert(self[0] != 0)
    if deg == -1: deg = len(a)
    mod = self.mod
    res = [pow(a[0], mod - 2, mod)]
    i = 1
    while i < deg:
        i <<= 1
        res = self.add(res, self.sub(res, self.mul(self.mul2(res), a[:i])[:i]))
    return res[:deg]
FPS.inv = inv

def exp(self: FPS, f: Poly, deg: int=-1) -> Poly:
    '''return: g s.t. log(g) == f (mod x ** deg)'''
    # assert(not self or self[0] == 0)
    if deg == -1: deg = len(f)
    ret = [1]
    i = 1
    while i < deg:
        i <<= 1
        ret = self.mul(ret, self.sub(self.add(f[:i], 1), self.log(ret, i)))[:i]
    return ret[:deg]
FPS.exp = exp

# https://nyaannyaan.github.io/library/fps/mod-pow.hpp
def mod_pow(k: int, base: Poly, d: Poly, mod: int, fps: FPS=None) -> Poly:
    assert(d)
    if not fps: fps = FPS(mod)
    inv = fps.inv(d[::-1])
    def quo(poly: Poly) -> Poly:
        if len(poly) < len(d): return []
        n = len(poly) - len(d) + 1
        return fps.mul(poly[:len(poly) - n - 1:-1], inv[:n])[n - 1::-1]

    res = [1]
    b = base[:]
    while k:
        if k & 1:
            res = fps.mul(res, b)
            res = fps.sub(res, fps.mul(quo(res), d))
            FPS.shrink(res)
        b = fps.mul2(b)
        b = fps.sub(b, fps.mul(quo(b), d))
        FPS.shrink(b)
        k >>= 1
        # assert(len(b) + 1 <= len(d))
        # assert(len(res) + 1 <= len(d))
    return res

# https://nyaannyaan.github.io/library/matrix/black-box-linear-algebra.hpp
def inner_product(a: Poly, b: Poly, mod: int) -> int:
    res = 0
    n = len(a)
    assert(n == len(b))
    for i in range(n): res += a[i] * b[i] % mod
    return res % mod

def random_poly(n: int, mod: int) -> Poly:
    return [randint(0, mod - 1) for _ in range(n)]

class ModMatrix:
    def __init__(self, n: int, mod: int) -> None:
        self.mat = [[0] * n for _ in range(n)]
        self.mod = mod

    def add(self, i: int, j: int, x: int) -> None:
        self.mat[i][j] += x

    def __mul__(self, r: Poly) -> Poly:
        assert(len(self.mat) == len(r))
        mod = self.mod
        return [sum(matij * r[j] % mod for j, matij in enumerate(mati)) % mod for mati in self.mat]

    def apply(self, i: int, r: int) -> None:
        mod = self.mod
        for j, matij in enumerate(self.mat[i]):
            self.mat[i][j] = matij * r % mod

class SparseMatrix:
    def __init__(self, n: int, mod: int) -> None:
        self.mat: List[List[int]] = [[] for _ in range(n)]
        self.mod = mod

    def add(self, i: int, j: int, x: int) -> None:
        self.mat[i].append(j << 30 | x)

    def __mul__(self, r: Poly) -> Poly:
        assert(len(self.mat) == len(r))
        mod = self.mod
        return [sum((jx & 0x3fffffff) * r[jx >> 30] % mod for jx in mati) % mod for mati in self.mat]

    def apply(self, i: int, r: int) -> None:
        mod = self.mod
        for idx, jx in enumerate(self.mat[i]):
            self.mat[i][idx] = (jx >> 30) << 30 | ((jx & 0x3fffffff) * r % mod)

def vector_minpoly(b: List[Poly], mod: int) -> Poly:
    assert(b)
    n = len(b); m = len(b[0])
    u = random_poly(m, mod)
    a = [0] * n
    for i, bi in enumerate(b): a[i] = inner_product(bi, u, mod)
    return berlekamp_massey(a, mod)

def mat_minpoly(A: Union[ModMatrix, SparseMatrix]) -> Poly:
    n = len(A.mat)
    u = random_poly(n, A.mod)
    b: List[Poly] = [0] * (n << 1 | 1)
    for i in range(len(b)):
        b[i] = u
        u = A * u
    return vector_minpoly(b, A.mod)

def fast_pow(A: Union[ModMatrix, SparseMatrix], b: Poly, k: int) -> Poly:
    n = len(b)
    mp = mat_minpoly(A)
    fps = FPS(A.mod)
    c = mod_pow(k, [0, 1], mp[::-1], A.mod, fps)
    res = [0] * n
    for ci in c:
        res = fps.add(res, fps.mul(b, ci))
        b = A * b
    return res

def fast_det(A: Union[ModMatrix, SparseMatrix]) -> int:
    n = len(A.mat)
    assert(n == len(A.mat))
    mod = A.mod
    D = random_poly(n, mod)
    while 1:
        while any([not x for x in D]): D = random_poly(n, mod)
        AD = deepcopy(A)
        for i, d in enumerate(D): AD.apply(i, d)
        mp = mat_minpoly(AD)
        if mp[-1] == 0: return 0
        if len(mp) != n + 1: continue
        det = -mp[-1] if n & 1 else mp[-1]
        Ddet = 1
        for d in D: Ddet = Ddet * d % mod
        return det * modinv(Ddet, mod) % mod
    exit(1)

# https://yukicoder.me/problems/no/1112
mod = 1_000_000_007
K, M, N = rd(), rd(), rd()
m = ModMatrix(K * K, mod)
for i in range(M):
    p, q, r = rd() - 1, rd() - 1, rd() - 1
    m.add(p * K + q, q * K + r, 1)
b = [0] * (K * K)
for i in range(K): b[i * K] = 1
res = fast_pow(m, b, N - 2)
wtn(sum(res[:K]))