;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam)))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
;;;
;;; ARRAY-ELEMENT-TYPE is not constant-folded on SBCL version earlier than
;;; 1.5.0. See
;;; https://github.com/sbcl/sbcl/commit/9f0d12e7ab961828931d01c0b2a76a5885ad35d2
;;;

(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-c:deftransform array-element-type ((array))
    (let ((type (sb-c::lvar-type array)))
      (flet ((element-type (type)
               (and (sb-c::array-type-p type)
                    (sb-int:neq (sb-kernel::array-type-specialized-element-type type) sb-kernel:*wild-type*)
                    (sb-kernel:type-specifier (sb-kernel::array-type-specialized-element-type type)))))
        (cond ((let ((type (element-type type)))
                 (and type
                      `',type)))
              ((sb-kernel:union-type-p type)
               (let (result)
                 (loop for type in (sb-kernel:union-type-types type)
                       for et = (element-type type)
                       unless (and et
                                   (if result
                                       (equal result et)
                                       (setf result et)))
                       do (sb-c::give-up-ir1-transform))
                 `',result))
              ((sb-kernel:intersection-type-p type)
               (loop for type in (sb-kernel:intersection-type-types type)
                     for et = (element-type type)
                     when et
                     return `',et
                     finally (sb-c::give-up-ir1-transform)))
              (t
               (sb-c::give-up-ir1-transform)))))))
;;;
;;; Arithmetic operations with dynamic modulus
;;;

(declaim ((unsigned-byte 32) *modulus*))
(defvar *modulus*)

(defun mod* (&rest args)
  (reduce (lambda (x y) (mod (* x y) *modulus*)) args))

(sb-c:define-source-transform mod* (&rest args)
  (if (null args)
      1
      (reduce (lambda (x y) `(mod (* ,x ,y) *modulus*)) args)))

(defun mod+ (&rest args)
  (reduce (lambda (x y) (mod (+ x y) *modulus*)) args))

(sb-c:define-source-transform mod+ (&rest args)
  (if (null args)
      0
      (reduce (lambda (x y) `(mod (+ ,x ,y) *modulus*)) args)))

(define-modify-macro incfmod (delta &optional (divisor '*modulus*))
  (lambda (x y divisor) (mod (+ x y) divisor)))

(define-modify-macro decfmod (delta &optional (divisor '*modulus*))
  (lambda (x y divisor) (mod (- x y) divisor)))

;;
;; Matrix multiplication over semiring
;;

(declaim (inline gemm))
(defun gemm (a b &key (op+ #'+) (op* #'*) (identity+ 0))
  "Calculates A*B. (OP+, OP*) must form a semiring. IDENTITY+ is the identity
element w.r.t. OP+."
  (declare ((simple-array * (* *)) a b)
           (function op+ op*))
  (let ((c (make-array (list (array-dimension a 0) (array-dimension b 1))
                       :element-type (array-element-type a))))
    (dotimes (row (array-dimension a 0))
      (dotimes (col (array-dimension b 1))
        (let ((res identity+))
          (dotimes (k (array-dimension a 1))
            (setf res
                  (funcall op+ res (funcall op* (aref a row k) (aref b k col)))))
          (setf (aref c row col) res))))
    c))

(declaim (inline matrix-power))
(defun matrix-power (base power &key (op+ #'+) (op* #'*) (identity+ 0) (identity* 1))
  (declare ((simple-array * (* *)) base)
           (function op+ op*)
           ((integer 0 #.most-positive-fixnum) power))
  (let ((size (array-dimension base 0)))
    (assert (= size (array-dimension base 1)))
    (let ((iden (make-array (array-dimensions base)
                            :element-type (array-element-type base)
                            :initial-element identity+)))
      (dotimes (i size)
        (setf (aref iden i i) identity*))
      (labels ((recur (p)
                 (declare ((integer 0 #.most-positive-fixnum) p))
                 (cond ((zerop p) iden)
                       ((evenp p)
                        (let ((res (recur (ash p -1))))
                          (gemm res res :op+ op+ :op* op* :identity+ identity+)))
                       (t
                        (gemm base (recur (- p 1))
                              :op+ op+ :op* op* :identity+ identity+)))))
        (recur power)))))

(declaim (inline gemv))
(defun gemv (a x &key (op+ #'+) (op* #'*) (identity+ 0))
  "Calculates A*x for a matrix A and a vector x. (OP+, OP*) must form a
semiring. IDENTITY+ is the identity element w.r.t. OP+."
  (declare ((simple-array * (* *)) a)
           ((simple-array * (*)) x)
           (function op+ op*))
  (let ((y (make-array (array-dimension a 0) :element-type (array-element-type x))))
    (dotimes (i (length y))
      (let ((res identity+))
        (dotimes (j (length x))
          (setf res
                (funcall op+ res (funcall op* (aref a i j) (aref x j)))))
        (setf (aref y i) res)))
    y))

(declaim (inline power-mod))
(defun power-mod (base power &optional (divisor 1000000007))
  "BASE := integer
POWER, DIVISOR := non-negative fixnum"
  (declare ((integer 0 #.most-positive-fixnum) divisor)
           (integer base))
  (labels ((recur (x p)
             (declare ((integer 0 #.most-positive-fixnum) x p))
             (cond ((zerop p) 1)
                   ((evenp p) (recur (mod (* x x) divisor) (ash p -1)))
                   (t (mod (* x (recur x (- p 1))) divisor)))))
    (declare (ftype (function * (values (integer 0 #.most-positive-fixnum) &optional))
                    recur))
    (recur (mod base divisor) power)))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

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

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (declare #.OPT)
  (let* ((l (read))
         (a (read))
         (b (read))
         (m (read))
         (boundaries (make-array 19 :element-type 'uint62 :initial-element 0)))
    (declare (uint62 l a b)
             (uint31 m)
             ((simple-array uint62 (*)) boundaries))
    (let ((*modulus* m))
      (dotimes (d 19)
        (setf (aref boundaries d)
              (max 0 (ceiling (- (expt 10 d) a) b))))
      (dotimes (d 19)
        (when (>= (aref boundaries d) l)
          (setf (aref boundaries d) l)
          (setf boundaries (adjust-array boundaries (+ d 1)))
          (return)))
      (let ((res 0))
        (declare (uint31 res))
        (loop for d from 1 below (length boundaries)
              for length = (- (aref boundaries d) (aref boundaries (- d 1)))
              for vec = (make-array 3 :element-type 'uint32)
              for mat = (make-array (list 3 3) :element-type 'uint32 :initial-element 0)
              do (setf (aref vec 0) 0
                       (aref vec 1) 0
                       (aref vec 2) 1)
                 (setf (aref mat 0 0) (mod (expt 10 d) m)
                       (aref mat 0 1) (mod b m)
                       (aref mat 0 2) (mod+ a (mod* b (aref boundaries (- d 1))))
                       (aref mat 1 1) 1
                       (aref mat 1 2) 1
                       (aref mat 2 2) 1)
                 (setq vec (gemv (matrix-power mat length
                                               :op+ #'mod+
                                               :op* #'mod*)
                                 vec
                                 :op+ #'mod+
                                 :op* #'mod*))
                 (setf res
                       (mod+ (mod* res (power-mod (expt 10 d) length m))
                             (aref vec 0))))
        (println res)))))

#-swank(main)


Measured memory_bytes: 45536