;; -*- 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))
                 (shadow :run)
                 (use-package :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
(declaim (inline power-mod))
(defun power-mod (base power &optional (divisor 1000000007))
  "BASE := integer
POWER, DIVISOR := non-negative fixnum"
  (declare ((unsigned-byte 32) divisor)
           (integer base))
  (labels ((recur (x p)
             (declare ((unsigned-byte 32) x)
                      ((unsigned-byte 62) 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 sum10 (k width divisor)
  (declare (uint62 k width)
           (uint31 divisor))
  (let ((factor (mod (expt 10 width) divisor)))
    (labels ((recur (k)
               (declare (uint62 k)
                        (values uint31))
               (cond ((zerop k) 0)
                     ((evenp k)
                      (mod (* (recur (ash k -1))
                              (+ 1 (power-mod factor (ash k -1) divisor)))
                           divisor))
                     (t
                      (mod (+ 1 (* factor (recur (- k 1))))
                           divisor)))))
      (recur k))))

(defun calc (k init delta width divisor)
  (declare (uint31 divisor)
           (uint62 k init delta width))
  (let ((factor (mod (expt 10 width) divisor)))
    (labels ((mod+ (x y) (mod (+ x y) divisor))
             (mod* (x y) (mod (* x y) divisor))
             (recur (k)
               (declare (uint62 k))
               (cond ((zerop k) 0)
                     ((evenp k)
                      (mod+ (mod* (mod* (ash k -1) delta)
                                  (sum10 (ash k -1) width divisor))
                            (mod* (+ 1 (power-mod factor (ash k -1) divisor))
                                  (recur (ash k -1)))))
                     (t (mod+ (mod* factor (recur (- k 1)))
                              (mod+ init (mod* (- k 1) delta)))))))
      (declare (inline mod+ mod*))
      (recur k))))

(defun main ()
  (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))
    (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))
      (loop for d from (position-if #'plusp boundaries) below (length boundaries)
            for length = (- (aref boundaries d) (aref boundaries (- d 1)))
            do (setf res
                     (mod
                      (+ (mod (* res (power-mod (expt 10 d) length m)) m)
                         (calc length (+ a (* b (aref boundaries (- d 1)))) b d m))
                      m)))
      (println res))))

#-swank(main)


Measured memory_bytes: 30308