;; -*- 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
;;;
;;; 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)))))))

(declaim (ftype (function * (values (unsigned-byte 16) &optional)) %mod-inverse))
(defun %mod-inverse (a modulus)
  "Solves ax ≡ 1 mod m. A and M must be coprime."
  (declare (optimize (speed 3))
           (integer a)
           ((integer 1 #.most-positive-fixnum) modulus))
  (labels ((%gcd (a b)
             (declare (optimize (safety 0))
                      ((integer 0 #.most-positive-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))))))))))
    (mod (%gcd (mod a modulus) modulus) modulus)))

;; Naive division
;; Reference: http://web.cs.iastate.edu/~cs577/handouts/polydivide.pdf
(declaim (inline poly-floor!))
(defun poly-floor! (u v modulus &optional quotient)
  "Returns the quotient q(x) and the remainder r(x) on Z/nZ: u(x) = q(x)v(x) + r(x),
deg(r) < deg(v). This function destructively modifies U. The time complexity is
O((deg(u)-deg(v))deg(v)).

The quotient is stored in QUOTIENT if it is given, otherwise a new vector is
created.

Note that MODULUS and V[deg(V)] must be coprime."
  (declare (vector u v)
           ((integer 1 #.most-positive-fixnum) modulus))
  ;; (assert (and (>= (length u) 1) (>= (length v) 1)))
  (let* ((m (loop for i from (- (length u) 1) downto 0
                  while (zerop (aref u i))
                  finally (return i)))
         (n (loop for i from (- (length v) 1) downto 0
                  unless (zerop (aref v i))
                  do (return i)
                  finally (error 'division-by-zero
                                 :operation #'poly-floor!
                                 :operands (list u v))))
         (quot (or quotient
                   (make-array (max 0 (+ 1 (- m n)))
                               :element-type (array-element-type u)))))
    (declare ((integer -1 (#.array-total-size-limit)) m n))
    (loop for k from (- m n) downto 0
          do (setf (aref quot k)
                   (mod (* (aref u (+ n k))
                           ;; FIXME: better to signal an error in non-coprime case?
                           (%mod-inverse (aref v n) modulus))
                        modulus))
             (loop for j from (+ n k -1) downto k
                   do (setf (aref u j)
                            (mod (- (aref u j)
                                    (mod (* (aref quot k) (aref v (- j k))) modulus))
                                 modulus))))
    (loop for i from (- (length u) 1) downto n
          do (setf (aref u i) 0)
          finally (return (values quot u)))))

;;;
;;; 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)
          (poly-floor! (copy-seq base)
                       (make-array 2 :element-type 'uint16
                                     :initial-contents `(,(- p pivot) 1))
                       p
                       quot)
          (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: 51688