(in-package #:cl-user)

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

(eval-when (:compile-toplevel :load-toplevel :execute)
  #+swank (declaim (optimize (speed 3) (safety 2)))
  #-swank (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 (ftype (function ((array * 2)) (array * 2)) copy-matrix))
(defun copy-matrix (matrix)
  (let ((new-mat (make-array (array-dimensions matrix)
                             :element-type (array-element-type matrix)
                             :adjustable (adjustable-array-p matrix))))
    (loop for i of-type fixnum below (array-dimension matrix 0)
          do (loop for j of-type fixnum below (array-dimension matrix 1)
                   do (setf (aref new-mat i j)
                            (aref matrix i j))))
    new-mat))

(declaim (ftype (function ((array * 2)) (array * 2)) rotate-matrix))
(defun rotate-matrix (matrix)
  " Return a matrix two-dimensional array rotated 90 degrees."
  (let ((m (array-dimension matrix 0))
        (n (array-dimension matrix 1)))
    (let ((new-mat (make-array (list n m)
                               :element-type (array-element-type matrix)
                               :adjustable (adjustable-array-p matrix))))
      (loop for i of-type fixnum below m
            do (loop for j of-type fixnum below n
                     do (setf (aref new-mat j (- m i 1))
                              (aref matrix i j))))
      new-mat)))

(declaim (ftype (function ((array * 2)) null) rotate-matrix!))
(defun rotate-matrix! (matrix)
  " Destructively rotate MATRIX."
  (destructuring-bind (m n) (array-dimensions matrix)
    (loop for i of-type fixnum below n
          do (loop for j of-type fixnum below m
                   do (rotatef (aref matrix j (- n i 1))
                               (aref matrix i j))))))

(declaim (ftype (function ((array * 2) (array * 2) &optional fixnum) (array * 2)) mat*))
(defun mat* (mat1 mat2 &optional modulo)
  (destructuring-bind (m n) (array-dimensions mat1)
    (destructuring-bind (p q) (array-dimensions mat2)
      (assert (= n p))
      (let ((new-mat (make-array (list m q)
                                 :element-type (array-element-type mat1)
                                 :adjustable (adjustable-array-p mat1))))
        (loop for i of-type fixnum below m
              do (loop for j of-type fixnum below q
                       do (setf (aref new-mat i j)
                                (loop for k of-type fixnum below n
                                      sum (if modulo
                                              (mod (* (aref mat1 i k)
                                                      (aref mat2 k j))
                                                   modulo)
                                              (* (aref mat1 i k)
                                                 (aref mat2 k j)))))))
        new-mat))))

(declaim (ftype (function ((array * 2) * &optional fixnum) (array * 2)) mat-pow))
(defun mat-pow (mat k &optional modulo)
  (destructuring-bind (m n) (array-dimensions mat)
    (assert (= m n))
    (let ((res (make-array (list m n)
                           :element-type (array-element-type mat)
                           :adjustable (adjustable-array-p mat)
                           :initial-element 0)))
      (loop for i of-type fixnum below n
            do (setf (aref res i i) 1))
      (sb-int:named-let rec ((k k)
                             (mat mat)
                             (res res))
        (cond ((<= k 0) res)
              ((oddp k) (rec (ash k -1)
                             (mat* mat mat modulo)
                             (mat* mat res modulo)))
              (t (rec (ash k -1)
                      (mat* mat mat modulo)
                      res)))))))


(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 main ()
  (let* ((n (read))
         (m (read))
         (time (read))
         (es (read-into m 'vector (lambda () (list (read) (read)))))
         (am (make-array (list n n))))
    (loop :for (a b) :across es
          :do (setf (aref am a b) 1)
              (setf (aref am b a) 1))
    (let* ((pow (mat-pow am time 998244353))
           (res (mat* (let ((tmp (make-array (list n n))))
                        (setf (aref tmp 0 0) 1)
                        tmp)
                      pow)))
      (println (aref res 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)))