;; -*- 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 (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)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(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
;;;
;;; Arithmetic operations with static modulus
;;;

(defmacro define-mod-operations (&optional (divisor 1000000007))
  `(progn
     (defun mod* (&rest args)
       (reduce (lambda (x y) (mod (* x y) ,divisor)) args))

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

     (defun mod+ (&rest args)
       (reduce (lambda (x y) (mod (+ x y) ,divisor)) args))

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

     (define-modify-macro incfmod (delta divisor)
       (lambda (x y divisor) (mod (+ x y) divisor)))

     (define-modify-macro decfmod (delta divisor)
       (lambda (x y divisor) (mod (- x y) divisor)))))

(define-mod-operations)

(defun main ()
  (declare #.OPT
           (inline digit-char-p))
  (let* ((s (coerce (the (simple-array character (*)) (read-line)) 'simple-base-string))
         (n (length s)) 
         (dp (make-array (list (+ n 1) 13) :element-type 'uint32 :initial-element 0)))
    (declare (simple-base-string s)
             (uint31 n))
    (setf (aref dp 0 0) 1)
    (do ((pos 0 (+ pos 1))
         (base 1 (mod (* base 10) 13)))
        ((= pos n))
      (declare (uint32 pos base))
      (if (char= #\? (aref s (- n pos 1)))
          (dotimes (d 10)
            (let ((num (mod (* d base) 13)))
              (dotimes (m 13)
                (incfmod (aref dp (+ pos 1) (mod (+ m num) 13))
                         (aref dp pos m)
                         +mod+))))
          (let* ((d (- (char-code (aref s (- n pos 1))) 48))
                 (num (mod (* d base) 13)))
            (declare (uint8 d))
            (dotimes (m 13)
              (setf (aref dp (+ pos 1) (mod (+ m num) 13))
                    (aref dp pos m))))))
    (println (aref dp n 5))))

#-swank (main)


Measured memory_bytes: 23016