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

(deftype fft-float () 'double-float)

(declaim (inline power2-p))
(defun power2-p (x)
  "Checks if X is a power of 2."
  (zerop (logand x (- x 1))))

;; For FFT of fixed length, preparing the table of cos(i*theta) and sin
;; (i*theta) will be efficient.
(defun %make-trifunc-table (n)
  (declare (optimize (speed 3) (safety 0))
           ((integer 0 #.most-positive-fixnum) n))
  (assert (power2-p n))
  (let* ((cos-table (make-array (ash n -2) :element-type 'fft-float))
         (sin-table (make-array (ash n -2) :element-type 'fft-float))
         (theta (/ (coerce (* 2 pi) 'fft-float) n)))
    (dotimes (i (ash n -2))
      (setf (aref cos-table i) (cos (* i theta))
            (aref sin-table i) (sin (* i theta))))
    (values cos-table sin-table)))

(defparameter *cos-table* nil)
(defparameter *sin-table* nil)

(defmacro with-fixed-length-fft (size &body body)
  "Makes FFT faster when the SIZE of target vectors is fixed in BODY. This macro
computes and holds the roots of unity for SIZE, which DFT! and INVERSE-DFT!
called in BODY automatically detects; they will signal an error when they
receive a vector of different size."
  (let ((s (gensym)))
    `(let ((,s ,size))
       (multiple-value-bind (*cos-table* *sin-table*) (%make-trifunc-table ,s)
         ,@body))))

(defun %dft-fixed-base! (f)
  (declare (optimize (speed 3) (safety 0))
           ((simple-array fft-float (*)) f))
  (prog1 f
    (let* ((n (length f))
           (cos-table *cos-table*)
           (sin-table *sin-table*)
           (factor n))
      (declare ((integer 0 #.most-positive-fixnum) factor)
               ((simple-array fft-float (*)) cos-table sin-table))
      (assert (power2-p n))
      (assert (= (ash n -2) (length cos-table)))
      ;; bit-reverse ordering
      (let ((i 0))
        (declare ((integer 0 #.most-positive-fixnum) i))
        (loop for j from 1 below (- n 1)
              do (loop for k of-type (integer 0 #.most-positive-fixnum)
                          = (ash n -1) then (ash k -1)
                       while (> k (setq i (logxor i k))))
                 (when (< j i)
                   (rotatef (aref f i) (aref f j)))))
      (do* ((mh 1 m)
            (m (ash mh 1) (ash mh 1)))
           ((> m n))
        (declare ((integer 0 #.most-positive-fixnum) mh m))
        (let ((mq (ash mh -1)))
          (setq factor (ash factor -1))
          (do ((jr 0 (+ jr m)))
              ((>= jr n))
            (declare ((integer 0 #.most-positive-fixnum) jr))
            (let ((xreal (aref f (+ jr mh))))
              (setf (aref f (+ jr mh)) (- (aref f jr) xreal))
              (incf (aref f jr) xreal)))
          (do ((i 1 (+ i 1)))
              ((>= i mq))
            (declare ((integer 0 #.most-positive-fixnum) i))
            (let* ((index (the fixnum (* factor i)))
                   (wreal (aref cos-table index))
                   (wimag (- (aref sin-table index))))
              (do ((j 0 (+ j m)))
                  ((>= j n))
                (let* ((j+mh (+ j mh))
                       (j+m-i (- (+ j m) i))
                       (xreal (+ (* wreal (aref f (+ j+mh i)))
                                 (* wimag (aref f j+m-i))))
                       (ximag (- (* wreal (aref f j+m-i))
                                 (* wimag (aref f (+ j+mh i))))))
                  (declare ((integer 0 #.most-positive-fixnum) j+mh j+m-i))
                  (setf (aref f (+ j+mh i))
                        (+ (- (aref f (- j+mh i))) ximag))
                  (setf (aref f j+m-i)
                        (+ (aref f (- j+mh i)) ximag))
                  (setf (aref f (- j+mh i))
                        (+ (aref f (+ j i)) (- xreal)))
                  (incf (aref f (+ j i)) xreal))))))))))

(defun %inverse-dft-fixed-base! (f)
  (declare (optimize (speed 3) (safety 0))
           ((simple-array fft-float (*)) f))
  (prog1 f
    (let* ((n (length f))
           (cos-table *cos-table*)
           (sin-table *sin-table*)
           (factor 1))
      (declare ((integer 0 #.most-positive-fixnum) factor)
               ((simple-array fft-float (*)) cos-table sin-table))
      (assert (power2-p n))
      (assert (= (ash n -2) (length cos-table)))
      (setf (aref f 0)
            (/ (aref f 0) 2))
      (setf (aref f (ash n -1))
            (/ (aref f (ash n -1)) 2))
      (do* ((m n mh)
            (mh (ash m -1) (ash m -1)))
           ((zerop mh))
        (declare ((integer 0 #.most-positive-fixnum) m mh))
        (let ((mq (ash mh -1)))
          (do ((jr 0 (+ jr m)))
              ((>= jr n))
            (declare ((integer 0 #.most-positive-fixnum) jr))
            (let ((xreal (- (aref f jr) (aref f (+ jr mh)))))
              (incf (aref f jr) (aref f (+ jr mh)))
              (setf (aref f (+ jr mh)) xreal)))
          (do ((i 1 (+ i 1)))
              ((>= i mq))
            (let* ((index (the fixnum (* factor i)))
                   (wreal (aref cos-table index))
                   (wimag (aref sin-table index)))
              (do ((j 0 (+ j m)))
                  ((>= j n))
                (let* ((j+mh (+ j mh))
                       (j+m-i (- (+ j m) i))
                       (xreal (- (aref f (+ j i)) (aref f (- j+mh i))))
                       (ximag (+ (aref f j+m-i) (aref f (+ j+mh i)))))
                  (declare ((integer 0 #.most-positive-fixnum) j+mh j+m-i))
                  (incf (aref f (+ j i)) (aref f (- j+mh i)))
                  (setf (aref f (- j+mh i))
                        (- (aref f j+m-i) (aref f (+ j+mh i))))
                  (setf (aref f (+ j+mh i))
                        (+ (* wreal xreal) (* wimag ximag)))
                  (setf (aref f j+m-i)
                        (- (* wreal ximag) (* wimag xreal))))))))
        (setq factor (ash factor 1)))
      ;; bit-reverse ordering
      (let ((i 0))
        (declare ((integer 0 #.most-positive-fixnum) i))
        (loop for j from 1 below (- n 1)
              do (loop for k of-type (integer 0 #.most-positive-fixnum)
                          = (ash n -1) then (ash k -1)
                       while (> k (setq i (logxor i k))))
                 (when (< j i)
                   (rotatef (aref f i) (aref f j))))))))

(declaim (inline dft!))
(defun dft! (f)
  (declare ((simple-array fft-float (*)) f))
  (if (zerop (length f))
      f
      (if *cos-table*
          (%dft-fixed-base! f)
          (error "Huh?"))))

(declaim (inline inverse-dft!))
(defun inverse-dft! (f)
  (declare ((simple-array fft-float (*)) f))
  (prog1 f
    (let ((n (length f)))
      (unless (zerop n)
        (let ((factor (* 2 (/ (coerce n 'fft-float)))))
          (if *cos-table*
              (%inverse-dft-fixed-base! f)
              (error "Huh?"))
          (dotimes (i n)
            (setf (aref f i) (* (aref f i) factor))))))))

(declaim (inline convolute!))
(defun convolute! (g h &optional result-vector)
  "Returns the convolution of two vectors G and H. A new vector is created when
RESULT-VECTOR is null. This function destructively modifies G and H. (They can
be restored by INVERSE-DFT!.)"
  (declare ((simple-array fft-float (*)) g h)
           ((or null (simple-array fft-float (*))) result-vector))
  (let ((n (length g)))
    (assert (and (power2-p n)
                 (= n (length h))))
    (dft! g)
    (dft! h)
    (let ((f (or result-vector (make-array n :element-type 'fft-float))))
      (unless (zerop n)
        (setf (aref f 0)
              (* (aref g 0) (aref h 0)))
        (setf (aref f (ash n -1))
              (* (aref g (ash n -1)) (aref h (ash n -1)))))
      (loop for i from 1 below (ash n -1)
            for value1 of-type fft-float
               = (- (* (aref g i) (aref h i))
                    (* (aref g (- n i)) (aref h (- n i))))
            for value2 of-type fft-float
               = (+ (* (aref g i) (aref h (- n i)))
                    (* (aref g (- n i)) (aref h i)))
            do (setf (aref f i) value1)
               (setf (aref f (- n i)) value2))
      (inverse-dft! f))))

(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 +fft-size+ :element-type 'uint16 :initial-element 0))
          (basef (make-array +fft-size+ :element-type 'double-float :initial-element 0d0))
          (base (make-array +fft-size+ :element-type 'uint16 :initial-element 0))
          (multiplier (make-array +fft-size+ :element-type 'double-float))
          (quot (make-array p :element-type 'uint16)))
      (setf (aref basef 0) 1d0)
      (with-fixed-length-fft +fft-size+
        (dotimes (i p)
          (fill multiplier 0d0)
          (setf (aref multiplier 0) (float (- i) 1d0))
          (setf (aref multiplier 1) 1d0)
          (convolute! basef multiplier basef)
          (dotimes (i +fft-size+)
            (setf (aref basef i)
                  (float (mod (the fixnum (round (aref basef i))) p) 1d0)))))
      (dotimes (i +fft-size+)
        (setf (aref base i) (round (aref basef i))))
      (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: 44392