(defconstant +mod107+ 1000000007) (defun %mod-mat-mul (n a b m) (let ((res (make-array `(,n ,n) :initial-element 0))) (dotimes (i n) (dotimes (j n) (dotimes (k n) (incf (aref res i j) (* (aref a i k) (aref b k j))) (setf (aref res i j) (mod (aref res i j) m))))) res)) (defun main (&rest argv) (declare (ignorable argv)) (let* ((a (read)) (b (read)) (n (read)) (A (make-array '(2 2) :initial-contents `((,a ,b) (1 0)))) (E (make-array '(2 2) :initial-contents `((1 0) (0 1)))) (m (1- n))) (when (<= n 1) (format t "~d~%" n) (return-from main)) (dotimes (i 30) (unless (zerop (logand 1 (ash m (- i)))) (setf E (%mod-mat-mul 2 A E +mod107+))) (setf A (%mod-mat-mul 2 A A +mod107+))) (format t "~d~%" (aref E 0 0)))) (main)