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

(defconstant +fft-size+ 4096)
(defun main ()
  (declare #.OPT)
  (let* ((p (read))
         ;; table of the indices such that a_i = 1
         (table1 (make-hash-table)))
    (declare (uint16 p))
    (dotimes (i p)
      (when (= (the bit (read)) 1)
        (setf (gethash i table1) t)))
    (let ((res (make-array p :element-type 'uint16 :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 p 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 (gethash pivot table1)
          (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)
            (setf (aref res i)
                  (mod (+ (aref res i) (aref quot 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: 18920