#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10005, mod = 998244353;
int n, m, s, t, x[N], y[N], cnt;
int T, A[N][N], re[N][N], mtx[N][N], tmp[N][N];
void pow(int y)
{
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++)
            if (i == j)
                re[i][j] = 1;
            else
                re[i][j] = 0;
    while (y)
    {
        if (y & 1)
        {
            for (int i = 1; i <= cnt; i++)
                for (int j = 1; j <= cnt; j++)
                    tmp[i][j] = 0;
            for (int i = 1; i <= cnt; i++)
                for (int j = 1; j <= cnt; j++)
                    for (int k = 1; k <= cnt; k++)
                        tmp[i][j] = (tmp[i][j] + re[i][k] * mtx[k][j] % mod) % mod;
            for (int i = 1; i <= cnt; i++)
                for (int j = 1; j <= cnt; j++)
                    re[i][j] = tmp[i][j];
        }
        y >>= 1;
        for (int i = 1; i <= cnt; i++)
            for (int j = 1; j <= cnt; j++)
                tmp[i][j] = 0;
        for (int i = 1; i <= cnt; i++)
            for (int j = 1; j <= cnt; j++)
                for (int k = 1; k <= cnt; k++)
                    tmp[i][j] = (tmp[i][j] + mtx[i][k] * mtx[k][j] % mod) % mod;
        for (int i = 1; i <= cnt; i++)
            for (int j = 1; j <= cnt; j++)
                mtx[i][j] = tmp[i][j];
    }
}
signed main()
{
    cin >> n >> m >> T;
    s = 1, t = n;
    x[++cnt] = 0, y[cnt] = s;
    for (int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        x[++cnt] = u, y[cnt] = v;
        x[++cnt] = v, y[cnt] = u;
    }
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++)
            if (i != j && i != (j ^ 1))
            {
                if (y[i] == x[j])
                    A[i][j] = 1;
            }
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++)
            mtx[i][j] = A[i][j];
    pow(T);
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
        if (y[i] == t)
            ans = (ans + re[1][i]) % mod;
    cout << ans << endl;
    return 0;
}

/tmp/ccBRZcNc.o: in function `pow(long long)':
answer.code:(.text+0x7): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccBRZcNc.o
/tmp/ccBRZcNc.o: in function `main':
answer.code:(.text.startup+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccBRZcNc.o
answer.code:(.text.startup+0x12): relocation truncated to fit: R_X86_64_PC32 against symbol `x' defined in .bss section in /tmp/ccBRZcNc.o
answer.code:(.text.startup+0x1e): relocation truncated to fit: R_X86_64_PC32 against symbol `y' defined in .bss section in /tmp/ccBRZcNc.o
answer.code:(.text.startup+0x49): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccBRZcNc.o
answer.code:(.text.startup+0x58): relocation truncated to fit: R_X86_64_PC32 against symbol `T' defined in .bss section in /tmp/ccBRZcNc.o
answer.code:(.text.startup+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccBRZcNc.o
answer.code:(.text.startup+0x6e): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccBRZcNc.o
answer.code:(.text.startup+0x76): relocation truncated to fit: R_X86_64_PC32 against symbol `s' defined in .bss section in /tmp/ccBRZcNc.o
answer.code:(.text.startup+0x81): relocation truncated to fit: R_X86_64_PC32 against symbol `t' defined in .bss section in /tmp/ccBRZcNc.o
answer.code:(.text.startup+0x88): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status