;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-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)))

     (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-modify-macro mulfmod (multiplier divisor)
       (lambda (x y divisor) (mod (* x y) divisor)))))

(define-mod-operations +mod+)

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (x (read))
         (y (read))
         (z (read))
         (ng-state (logior (ash 1 (+ x y z -1)) (ash 1 (+ y z -1)) (ash 1 (+ z -1))))
         (mask (- (ash 1 (+ x y z)) 1))
         (dp (make-array (list (+ 1 n) (ash 1 (+ x y z)))
                         :element-type 'uint32
                         :initial-element 0)))
    (declare (uint8 n)
             ((integer 1 7) x y z))
    (setf (aref dp 0 0) 1)
    ;; (format t "~17,'0B~%~17,'0B~%" ng-state mask)
    (dotimes (i n)
      (dotimes (bits (ash 1 (+ x y z)))
        (unless (= ng-state (logand bits ng-state))
          (loop for a from 1 to 10
                for new-bits = (logand mask (logior (ash bits a) (ash 1 (- a 1))))
                unless (= ng-state (logand new-bits ng-state))
                do ;; (format t "~2d ~17,'0B~%" a new-bits)
                   (incfmod (aref dp (+ i 1) new-bits)
                            (aref dp i bits)
                            +mod+)))))
    (println (mod- (mod (expt 10 n) +mod+)
                   (loop with res of-type uint32 = 0
                         for bits below (ash 1 (+ x y z))
                         do (incfmod res (aref dp n bits) +mod+)
                         finally (return res))))))

#-swank (main)


Measured memory_bytes: 37348