(in-package #:cl-user)

;;------------------------------Preferences------------------------------

(eval-when (:compile-toplevel :load-toplevel :execute)
  (declaim (optimize (speed 3) (safety 0) (debug 0)))
  #+swank (load "~/ghq/github.com/motoshira/atcoder-submission/ac-tools/act.lisp")
  #+swank (ql:quickload :prove)
  #-swank (declaim (sb-ext:muffle-conditions sb-ext:compiler-note))
  #-swank (sb-ext:disable-debugger)
  (pushnew :inline-generic-funcion *features*))

;;;
;;; Beginning of inserted contents
;;;

;; modint functions

(defpackage #:modint
  (:use #:cl)
  (:nicknames #:m #:mod)
  (:shadow #:+
           #:-
           #:*
           #:/)
  (:export #:*mod*
           #:modint
           #:+
           #:-
           #:*
           #:/
           #:mod-inv
           #:mod-power
           #:make-mod-fact-table
           #:mod-combi-with-table
           #:incmodf
           #:decmodf
           #:mulmodf
           #:divmodf))

(in-package #:modint)

(declaim (fixnum *mod*))
(defvar *mod* 1000000007)

(declaim (inline modint)
         (ftype (function (integer) fixnum) modint))
(defun modint (integer)
  ;; (integer) -> (fixnum)
  ;; TODO TLE on big negative integer
  (declare (integer integer))
  (loop while (minusp integer)
        do (incf integer *mod*))
  (the fixnum
       (if (< integer *mod*)
           integer
           (mod integer *mod*))))

(defun %operate (fn args)
  (declare ((function (fixnum fixnum) fixnum) fn))
  (if (null args)
      0
      (reduce (lambda (x y)
                (modint (funcall fn x (modint y))))
              (rest args)
              :initial-value (first args))))

(defun + (&rest args)
  (%operate (lambda (x y)
              (cl:+ x y))
            args))

(defun - (&rest args)
  (%operate (lambda (x y)
              (cl:- x y))
            args))

(defun * (&rest args)
  (%operate (lambda (x y)
              (cl:* x y))
            args))

(defun / (&rest args)
  (%operate (lambda (x y)
              (cl:* x (mod-inv y)))
            args))

;; TODO compiler-macro

(defmacro %expand (fn x y)
  `(modint (funcall (the (function (fixnum fixnum) fixnum)
                         ,fn)
                    ,x
                    (modint ,y))))

(define-compiler-macro m:+ (&whole form &rest args)
  (if (> (length args) 10)
      form
      (reduce (lambda (acc x)
                `(%expand (lambda (x y)
                            (declare (fixnum x y))
                            (cl:+ x y))
                          ,acc
                          ,x))
              (rest args)
              :initial-value `(modint ,(first args)))))

(define-compiler-macro m:- (&whole form &rest args)
  (if (> (length args) 10)
      form
      (reduce (lambda (acc x)
                `(%expand (lambda (x y)
                            (declare (fixnum x y))
                            (cl:- x y))
                          ,acc
                          ,x))
              (rest args)
              :initial-value `(modint ,(first args)))))

(define-compiler-macro m:* (&whole form &rest args)
  (if (> (length args) 10)
      form
      (reduce (lambda (acc x)
                `(%expand (lambda (x y)
                            (declare (fixnum x y))
                            (cl:* x y))
                          ,acc
                          ,x))
              (rest args)
              :initial-value `(modint ,(first args)))))

(define-compiler-macro m:/ (&whole form &rest args)
  (if (> (length args) 10)
      form
      (reduce (lambda (acc x)
                `(%expand (lambda (x y)
                            (declare (fixnum x y))
                            (cl:* x (mod-inv y)))
                          ,acc
                          ,x))
              (rest args)
              :initial-value `(modint ,(first args)))))

(declaim (ftype (function (fixnum) fixnum) mod-inv))
(defun mod-inv (a)
  "Reference:https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a"
  (declare (fixnum a))
  (let ((b *mod*)
        (u 1)
        (v 0))
    (declare (fixnum b u v))
    (loop until (zerop b) do
      (let ((w (truncate a b)))
        (decf (the fixnum a) (the fixnum
                                  (cl:* (the fixnum w)
                                        (the fixnum b))))
        (rotatef (the fixnum a)
                 (the fixnum b))
        (decf (the fixnum u)
              (the fixnum
                   (cl:* (the fixnum w)
                         (the fixnum v))))
        (rotatef u v)))
    (modint u)))

(declaim (ftype (function (fixnum (integer 0)) fixnum) mod-power)
         (inline mod-power))
(defun mod-power (base power)
  ;; Reference:https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
  (declare (fixnum base)
           ((integer 0) power))
  (loop while (plusp power)
        with res of-type fixnum = 1
        do (psetq base (the fixnum (* base base))
                  power (the (integer 0) (ash power -1))
                  res (the fixnum (if (logbitp 0 power)
                                    (* res base)
                                    res)))
        finally (return res)))

(define-modify-macro incmodf (&optional (val 1)) (lambda (place val) (+ place val)))
(define-modify-macro decmodf (&optional (val 1)) (lambda (place val) (- place val)))
(define-modify-macro mulmodf (&optional (val 1)) (lambda (place val) (* place val)))
(define-modify-macro divmodf (&optional (val 1)) (lambda (place val) (/ place val)))

(declaim (ftype (function (fixnum) (simple-array fixnum 1)) make-mod-table)
         (inline make-mod-fact-table))
(defun make-mod-fact-table (size)
  (declare (fixnum size))
  (let ((table (make-array (1+ size)
                           :element-type 'fixnum)))
    (declare ((simple-array fixnum 1) table))
    (setf (aref table 0) 1)
    (loop for i of-type fixnum below size
          do (setf (aref table (1+ i))
                   (* (aref table i)
                      (the fixnum (1+ i)))))
    table))

(declaim (ftype (function (fixnum fixnum (simple-array fixnum 1)) fixnum) mod-combi-with-table)
         (inline mod-combi-with-table))
(defun mod-combi-with-table (n k table)
  (declare (fixnum n k)
           ((simple-array fixnum 1) table))
  (the fixnum
       (if (or (< n k)
               (< n 0)
               (< k 0))
           0
           (/ (aref table n)
              (aref table k)
              (aref table (the fixnum (cl:- n k)))))))


;;;
;;; End of inserted contents
;;;

;;---------------------------------Body---------------------------------

(in-package #:cl-user)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 obj
      (princ obj stream)
      (terpri stream))))

(defun read-into (count &optional (result-type 'list) (reader #'read))
  (coerce (loop :repeat count :collect (funcall reader)) result-type))

(defun mat* (m1 m2)
  (declare ((simple-array fixnum (* *)) m1 m2))
  (let* ((n (array-dimension m1 0))
         (res (make-array (list n n) :element-type 'fixnum)))
    (declare ((simple-array fixnum (* *)) res))
    (declare (fixnum n))
    (loop :for i :of-type fixnum :below n
          :do (loop :for j :of-type fixnum :below n
                    :for tmp :of-type fixnum := 0
                    :do (loop :for k :of-type fixnum :below n
                              :do (m:incmodf (the fixnum tmp)
                                      (m:* (aref m1 i k)
                                           (aref m2 k j))))
                        (setf (aref res i j) tmp)))
    res))

(defun main ()
  (let* ((m:*mod* 998244353)
         (n (read))
         (m (read))
         (time (read))
         (es (read-into m 'vector (lambda () (list (read) (read)))))
         (am (make-array (list n n) :element-type 'fixnum
                                    :initial-element 0)))
    (declare (fixnum n m time)
             ((simple-array fixnum (* *)) am))
    (loop :for (a b) :across es
          :do (setf (aref am a b) 1)
              (setf (aref am b a) 1))
    (let* ((dub (make-array 61)))
      (declare ((simple-array t (*)) dub))
      (setf (aref dub 0) am)
      (dotimes (d 60)
        (setf (aref dub (1+ d))
              (mat* (aref dub d)
                    (aref dub d))))
      (let ((bm (make-array (list n n) :element-type 'fixnum
                                       :initial-element 0))
            (d 0)
            (k time))
        (declare ((simple-array fixnum (* *)) bm)
                 (fixnum d k))
        (dotimes (i n)
          (setf (aref bm i i) 1))
        (loop :while (plusp k)
              :do (psetf (the fixnum k) (the fixnum (ash k -1))
                         (the (simple-array fixnum (* *)) bm)
                         (if (oddp k)
                             (mat* (aref dub d)
                                   bm)
                             bm)
                         (the fixnum d) (the fixnum (1+ d))))
        (println (aref bm 0 0))))))

#-swank (main)

#+swank
(defun run ()
  (let ((*standard-input*
          (make-string-input-stream
           (with-output-to-string (*standard-output*)
             (run-program
              (merge-pathnames "copy-or-paste" (truename "~/bin/"))
              '()
              :output *standard-output*)))))
    (main)))