;; -*- 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
;;;
;;; Modular arithmetic
;;;

(declaim (ftype (function * (values fixnum fixnum &optional)) %gcd))
(defun %gcd (a b)
  (declare (optimize (speed 3) (safety 0))
           (fixnum a b))
  (if (zerop b)
      (values 1 0)
      (multiple-value-bind (p q) (floor a b) ; a = pb + q
        (multiple-value-bind (v u) (%gcd b q)
          (declare (fixnum u v))
          (values u (the fixnum (- v (the fixnum (* p u)))))))))

(declaim (ftype (function * (values (mod #.most-positive-fixnum) &optional)) mod-inverse))
(defun mod-inverse (a modulus)
  "Solves ax ≡ 1 mod m. A and M must be coprime."
  (declare #.OPT
           ((unsigned-byte 32) a modulus))
  (mod (%gcd (mod a modulus) modulus) modulus))

(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

(declaim (inline poly-value))
(defun poly-value (poly input divisor)
  (let ((x^i 1)
        (res 0))
    (declare (fixnum x^i res))
    (dotimes (i (length poly))
      (setq res (mod (+ res (* x^i (aref poly i))) divisor))
      (setq x^i (mod (* x^i input) divisor)))
    res))

(defun main ()
  (declare #.OPT)
  (let* ((p (read))
         (as (make-array p :element-type 'bit)))
    (declare (uint16 p))
    (dotimes (i p)
      (setf (aref as i) (read)))
    (let ((res (make-array p :element-type 'uint32 :initial-element 0))
          (base (make-array (+ p 1) :element-type 'uint16 :initial-element 0))
          (quot (make-array p :element-type 'uint16)))
      (setf (aref base 0) 1)
      (dotimes (i p)
        (loop for j from (+ i 1) above 0
              do (setf (aref base j)
                       (mod (- (aref base (- j 1))
                               (* i (aref base j)))
                            p)))
        (setf (aref base 0) (mod (- (* i (aref base 0))) p)))
      (dotimes (pivot p)
        (when (= 1 (aref as pivot))
          (fill quot 0)
          (setf (aref quot (- p 1)) (aref base p))
          (loop for i from (- p 2) downto 0
                do (setf (aref quot i)
                         (mod (+ (aref base (+ i 1))
                                 (* pivot (aref quot (+ i 1))))
                              p)))
          (let ((factor (mod-inverse (poly-value quot pivot p) p)))
            (declare (uint16 factor))
            (dotimes (i p)
              (setf (aref quot i)
                    (mod (* factor (aref quot i)) p))))
          (dotimes (i p)
            (incf (aref res i) (aref quot i)))))
      (dotimes (i p)
        (setf (aref res i) (mod (aref res i) p)))
      (let ((init t))
        (dotimes (i p)
          (if init (setq init nil) (write-char #\ ))
          (princ (aref res i)))
        (terpri)))))

#-swank (main)


Measured memory_bytes: 19172