(in-package :cl-user)
(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 :cp/util) :silent t)
  #+swank (use-package :cp/util :cl-user)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (set-dispatch-macro-character #\# #\> #'cl-debug-print:debug-print-reader)

(macrolet ((def (b)
             `(progn (deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))
                     (deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))))
           (define-int-types (&rest bits) `(progn ,@(mapcar (lambda (b) `(def ,b)) bits))))
  (define-int-types 2 4 7 8 15 16 31 32 62 63 64))

(defconstant +mod+ 998244353)

(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)))

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

;; BEGIN_INSERTED_CONTENTS
;;;
;;; Arithmetic operations with static modulus
;;;

(defpackage :cp/mod-operations
  (:use :cl)
  (:export #:define-mod-operations))
(in-package :cp/mod-operations)

;; NOTE: Currently MOD* and MOD+ doesn't apply MOD when the number of
;; parameters is one. For simplicity I won't fix it for now.
(defmacro define-mod-operations (divisor &optional (package (sb-int:sane-package)))
  (let ((mod* (intern "MOD*" package))
        (mod+ (intern "MOD+" package))
        (incfmod (intern "INCFMOD" package))
        (decfmod (intern "DECFMOD" package))
        (mulfmod (intern "MULFMOD" package)))
    `(progn
       (defun ,mod* (&rest args)
         (reduce (lambda (x y) (mod (* x y) ,divisor)) args))

       (defun ,mod+ (&rest args)
         (reduce (lambda (x y) (mod (+ x y) ,divisor)) args))

       #+sbcl
       (eval-when (:compile-toplevel :load-toplevel :execute)
         (locally (declare (sb-ext:muffle-conditions warning))
           (sb-c:define-source-transform ,mod* (&rest args)
             (if (null args)
                 1
                 (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)
         (lambda (x y) (mod (+ x y) ,divisor)))

       (define-modify-macro ,decfmod (delta)
         (lambda (x y) (mod (- x y) ,divisor)))

       (define-modify-macro ,mulfmod (multiplier)
         (lambda (x y) (mod (* x y) ,divisor))))))

(define-mod-operations cl-user::+mod+ :cl-user)

;;;
;;; Binomial coefficient with mod
;;; build: O(n)
;;; query: O(1)
;;;

(defpackage :cp/binomial-coefficient-mod
  (:use :cl)
  (:export #:binom #:perm #:multinomial #:stirling2 #:catalan #:+binom-mod+
           #:*fact* #:*fact-inv* #:*inv*))
(in-package :cp/binomial-coefficient-mod)

;; TODO: non-global handling

(defconstant +binom-size+ 510000)
(defconstant +binom-mod+ (if (boundp 'cl-user::+mod+)
                             (symbol-value 'cl-user::+mod+)
                             #.(+ (expt 10 9) 7)))

(sb-ext:define-load-time-global *fact*
  (make-array +binom-size+ :element-type '(unsigned-byte 31))
  "table of factorials")
(sb-ext:define-load-time-global *fact-inv*
  (make-array +binom-size+ :element-type '(unsigned-byte 31))
  "table of inverses of factorials")
(sb-ext:define-load-time-global *inv*
  (make-array +binom-size+ :element-type '(unsigned-byte 31))
  "table of inverses of non-negative integers")
(declaim ((simple-array (unsigned-byte 31) (*)) *fact* *fact-inv* *inv*))

(defun initialize-binom ()
  (declare (optimize (speed 3) (safety 0)))
  (setf (aref *fact* 0) 1
        (aref *fact* 1) 1
        (aref *fact-inv* 0) 1
        (aref *fact-inv* 1) 1
        (aref *inv* 1) 1)
  (loop for i from 2 below +binom-size+
        do (setf (aref *fact* i) (mod (* i (aref *fact* (- i 1))) +binom-mod+)
                 (aref *inv* i) (- +binom-mod+
                                   (mod (* (aref *inv* (rem +binom-mod+ i))
                                           (floor +binom-mod+ i))
                                        +binom-mod+))
                 (aref *fact-inv* i) (mod (* (aref *inv* i)
                                             (aref *fact-inv* (- i 1)))
                                          +binom-mod+))))

(initialize-binom)

(declaim (inline binom))
(defun binom (n k)
  "Returns nCk."
  (if (or (< n k) (< n 0) (< k 0))
      0
      (mod (* (aref *fact* n)
              (mod (* (aref *fact-inv* k) (aref *fact-inv* (- n k))) +binom-mod+))
           +binom-mod+)))

(declaim (inline perm))
(defun perm (n k)
  "Returns nPk."
  (if (or (< n k) (< n 0) (< k 0))
      0
      (mod (* (aref *fact* n) (aref *fact-inv* (- n k))) +binom-mod+)))

;; TODO: compiler macro or source-transform
(declaim (inline multinomial))
(defun multinomial (&rest ks)
  "Returns the multinomial coefficient K!/k_1!k_2!...k_n! for K = k_1 + k_2 +
... + k_n. K must be equal to or smaller than
MOST-POSITIVE-FIXNUM. (multinomial) returns 1."
  (let ((sum 0)
        (result 1))
    (declare ((integer 0 #.most-positive-fixnum) result sum))
    (dolist (k ks)
      (incf sum k)
      (setq result
            (mod (* result (aref *fact-inv* k)) +binom-mod+)))
    (mod (* result (aref *fact* sum)) +binom-mod+)))

(declaim (inline stirling2))
(defun stirling2 (n k)
  "Returns the stirling number of the second kind S2(n, k). Time complexity is
O(klog(n))."
  (declare ((integer 0 #.most-positive-fixnum) n k))
  (labels ((mod-power (base exp)
             (declare ((integer 0 #.most-positive-fixnum) base exp))
             (loop with res of-type (integer 0 #.most-positive-fixnum) = 1
                   while (> exp 0)
                   when (oddp exp)
                   do (setq res (mod (* res base) +binom-mod+))
                   do (setq base (mod (* base base) +binom-mod+)
                            exp (ash exp -1))
                   finally (return res))))
    (loop with result of-type fixnum = 0
          for i from 0 to k
          for delta = (mod (* (binom k i) (mod-power i n)) +binom-mod+)
          when (evenp (- k i))
          do (incf result delta)
             (when (>= result +binom-mod+)
               (decf result +binom-mod+))
          else
          do (decf result delta)
             (when (< result 0)
               (incf result +binom-mod+))
          finally (return (mod (* result (aref *fact-inv* k)) +binom-mod+)))))

(declaim (inline catalan))
(defun catalan (n)
  "Returns the N-th Catalan number."
  (declare ((integer 0 #.most-positive-fixnum) n))
  (mod (* (aref *fact* (* 2 n))
          (mod (* (aref *fact-inv* (+ n 1))
                  (aref *fact-inv* n))
               +binom-mod+))
       +binom-mod+))

;;;
;;; Fast Number Theoretic Transform
;;; Reference:
;;; https://github.com/ei1333/library/blob/master/math/fft/number-theoretic-transform-friendly-mod-int.cpp
;;; https://github.com/atcoder/ac-library/tree/master/atcoder
;;;

(defpackage :cp/ntt
  (:use :cl)
  (:export #:define-ntt #:check-ntt-vector #:ntt-int #:ntt-vector #:+ntt-mod+))
(in-package :cp/ntt)

(deftype ntt-int () '(unsigned-byte 31))
(deftype ntt-vector () '(simple-array ntt-int (*)))

(eval-when (:compile-toplevel :load-toplevel :execute)
  (declaim (inline %tzcount))
  (defun %tzcount (x)
    "Returns the number of trailing zero bits. Note that (%TZCOUNT 0) = -1."
    (- (integer-length (logand x (- x))) 1))
  (defun %mod-power (base exp modulus)
    (declare (ntt-int base exp modulus))
    (let ((res 1))
      (declare (ntt-int res))
      (loop while (> exp 0)
            when (oddp exp)
            do (setq res (mod (* res base) modulus))
            do (setq base (mod (* base base) modulus)
                     exp (ash exp -1)))
      res))
  (defun %mod-inverse (x modulus)
    (%mod-power x (- modulus 2) modulus))
  (defun %calc-generator (modulus)
    "MODULUS must be prime."
    (declare (ntt-int modulus))
    (assert (>= modulus 2))
    (case modulus
      (2 1)
      (167772161 3)
      (469762049 3)
      (754974721 11)
      (998244353 3)
      (otherwise
       (let ((divs (make-array 20 :element-type 'ntt-int :initial-element 0))
             (count 1)
             (x (floor (- modulus 1) 2)))
         (declare ((integer 0 #.most-positive-fixnum) x))
         (setf (aref divs 0) 2)
         (loop while (evenp x)
               do (setq x (floor x 2)))
         (loop for i of-type ntt-int from 3 by 2
               while (<= (* i i) x)
               when (zerop (mod x i))
               do (setf (aref divs count) i)
                  (incf count)
                  (loop while (zerop (mod x i))
                        do (setq x (floor x i))))
         (when (> x 1)
           (setf (aref divs count) x)
           (incf count))
         (loop for g of-type ntt-int from 2
               for ok = t
               do (dotimes (i count)
                    (when (= 1 (%mod-power g (floor (- modulus 1) (aref divs i)) modulus))
                      (setq ok nil)
                      (return)))
               when ok
               do (return g)))))))

;; KLUDGE: This function depends on SBCL's behaviour. Actually ADJUST-ARRAY
;; isn't guaranteed to preserve the given VECTOR.
(declaim (ftype (function * (values ntt-vector &optional)) %adjust-array))
(defun %adjust-array (vector length)
  (declare (vector vector))
  (let ((vector (coerce vector 'ntt-vector)))
    (if (= (length vector) length)
        (copy-seq vector)
        (adjust-array vector length :initial-element 0))))

(defun check-ntt-vector (vector)
  (declare (optimize (speed 3))
           (vector vector))
  (let ((len (length vector)))
    (assert (zerop (logand len (- len 1)))) ;; power of two
    (check-type len ntt-int)))

(defmacro define-ntt (modulus &key ntt inverse-ntt convolve mod-inverse mod-power)
  (let* ((ntt (or ntt (intern "NTT!")))
         (inverse-ntt (or inverse-ntt (intern "INVERSE-NTT!")))
         (convolve (or convolve (intern "CONVOLVE")))
         (mod-power (or mod-power (gensym "MOD-POWER")))
         (mod-inverse (or mod-inverse (gensym "MOD-INVERSE")))
         (ntt-base (gensym "*NTT-BASE*"))
         (ntt-inv-base (gensym "*NTT-INV-BASE*"))
         (base-size (%tzcount (- modulus 1)))
         (root (%calc-generator modulus)))
    (assert (typep modulus 'ntt-int))
    `(progn
       (declaim (inline ,mod-power))
       (defun ,mod-power (base exp)
         (declare (ntt-int base)
                  ((integer 0 #.most-positive-fixnum) exp))
         (let ((res 1))
           (declare (ntt-int res))
           (loop while (> exp 0)
                 when (oddp exp)
                 do (setq res (mod (* res base) ,modulus))
                 do (setq base (mod (* base base) ,modulus)
                          exp (ash exp -1)))
           res))
       (declaim (inline ,mod-inverse))
       (defun ,mod-inverse (x)
         (,mod-power x (- ,modulus 2)))
       (declaim (ntt-vector ,ntt-base ,ntt-inv-base))
       (sb-ext:define-load-time-global ,ntt-base
         (make-array ,base-size :element-type 'ntt-int))
       (sb-ext:define-load-time-global ,ntt-inv-base
         (make-array ,base-size :element-type 'ntt-int))
       (dotimes (i ,base-size)
         (setf (aref ,ntt-base i)
               (mod (- (%mod-power ,root (ash (- ,modulus 1) (- (+ i 2))) ,modulus))
                    ,modulus)
               (aref ,ntt-inv-base i)
               (%mod-inverse (aref ,ntt-base i) ,modulus)))

       (declaim (ftype (function * (values ntt-vector &optional)) ,ntt))
       (defun ,ntt (vector)
         (declare (optimize (speed 3) (safety 0))
                  (vector vector))
         (check-ntt-vector vector)
         (labels ((mod* (x y) (mod (* x y) ,modulus))
                  (mod+ (x y)
                    (let ((res (+ x y)))
                      (if (>= res ,modulus)
                          (- res ,modulus)
                          res)))
                  (mod- (x y) (mod+ x (- ,modulus y))))
           (declare (inline mod* mod+ mod-))
           (let* ((vector (coerce vector 'ntt-vector))
                  (len (length vector))
                  (base ,ntt-base))
             (declare (ntt-vector vector base)
                      (ntt-int len))
             (when (<= len 1)
               (return-from ,ntt vector))
             (loop for m of-type ntt-int = (ash len -1) then (ash m -1)
                   while (> m 0)
                   for w of-type ntt-int = 1
                   for k of-type ntt-int = 0
                   do (loop for s of-type ntt-int from 0 below len by (* 2 m)
                            do (loop for i from s below (+ s m)
                                     for j from (+ s m)
                                     for x = (aref vector i)
                                     for y = (mod* (aref vector j) w)
                                     do (setf (aref vector i) (mod+ x y)
                                              (aref vector j) (mod- x y)))
                               (incf k)
                               (setq w (mod* w (aref base (%tzcount k))))))
             vector)))

       (declaim (ftype (function * (values ntt-vector &optional)) ,inverse-ntt))
       (defun ,inverse-ntt (vector &optional inverse)
         (declare (optimize (speed 3) (safety 0))
                  (vector vector))
         (check-ntt-vector vector)
         (labels ((mod* (x y)
                    (declare (ntt-int x y))
                    (mod (* x y) ,modulus))
                  (mod+ (x y)
                    (declare (ntt-int x y))
                    (let ((res (+ x y)))
                      (if (>= res ,modulus)
                          (- res ,modulus)
                          res)))
                  (mod- (x y)
                    (declare (ntt-int x y))
                    (mod+ x (- ,modulus y))))
           (declare (inline mod* mod+ mod-))
           (let* ((vector (coerce vector 'ntt-vector))
                  (len (length vector))
                  (base ,ntt-inv-base))
             (declare (ntt-vector vector base)
                      (ntt-int len))
             (when (<= len 1)
               (return-from ,inverse-ntt vector))
             (loop for m of-type ntt-int = 1 then (ash m 1)
                   while (< m len)
                   for w of-type ntt-int = 1
                   for k of-type ntt-int = 0
                   do (loop for s of-type ntt-int from 0 below len by (* 2 m)
                            do (loop for i from s below (+ s m)
                                     for j from (+ s m)
                                     for x = (aref vector i)
                                     for y = (aref vector j)
                                     do (setf (aref vector i) (mod+ x y)
                                              (aref vector j) (mod* (mod- x y) w)))
                               (incf k)
                               (setq w (mod* w (aref base (%tzcount k))))))
             (when inverse
               (let ((inv-len (,mod-power len (- ,modulus 2))))
                 (dotimes (i len)
                   (setf (aref vector i) (mod* inv-len (aref vector i))))))
             vector)))

       (declaim (ftype (function * (values ntt-vector &optional)) ,convolve))
       (defun ,convolve (vector1 vector2)
         (declare (optimize (speed 3))
                  (vector vector1 vector2))
         (let ((len1 (length vector1))
               (len2 (length vector2)))
           (when (or (zerop len1) (zerop len2))
             (return-from ,convolve (make-array 0 :element-type 'ntt-int)))
           (let* ((mul-len (max 0 (- (+ len1 len2) 1)))
                  ;; power of two ceiling
                  (required-len (ash 1 (integer-length (max 0 (- mul-len 1)))))
                  (vector1 (,ntt (%adjust-array vector1 required-len)))
                  (vector2 (,ntt (%adjust-array vector2 required-len))))
             (declare ((mod #.array-total-size-limit) mul-len))
             (dotimes (i required-len)
               (setf (aref vector1 i)
                     (mod (* (aref vector1 i) (aref vector2 i)) ,modulus)))
             (adjust-array (,inverse-ntt vector1 t) mul-len)))))))

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defconstant +ntt-mod+ 998244353))

#+(or)
(define-ntt #.+ntt-mod+)

(defpackage :cp/read-fixnum
  (:use :cl)
  (:export #:read-fixnum))
(in-package :cp/read-fixnum)

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setq minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48)
                              (* 10 (the (integer 0 #.(floor most-positive-fixnum 10))
                                         result))))
              (return (if minus (- result) result))))))))

(defpackage :cp/polynomial-ntt
  (:use :cl :cp/ntt)
  (:export #:poly-multiply #:poly-inverse #:poly-floor #:poly-mod #:poly-sub #:poly-add
           #:multipoint-eval #:poly-total-prod))
(in-package :cp/polynomial-ntt)

(define-ntt #.+ntt-mod+
  :convolve poly-multiply
  :mod-inverse %mod-inverse)

(declaim (ftype (function * (values ntt-vector &optional)) poly-inverse))
(defun poly-inverse (poly &optional result-length)
  (declare (optimize (speed 3))
           (vector poly)
           ((or null fixnum) result-length))
  (let* ((poly (coerce poly 'ntt-vector))
         (n (length poly)))
    (declare (ntt-vector poly))
    (when (or (zerop n)
              (zerop (aref poly 0)))
      (error 'division-by-zero
             :operation #'poly-inverse
             :operands poly))
    (let ((res (make-array 1
                           :element-type 'ntt-int
                           :initial-element (%mod-inverse (aref poly 0))))
          (result-length (or result-length n)))
      (declare (ntt-vector res))
      (loop for i of-type ntt-int = 1 then (ash i 1)
            while (< i result-length)
            for decr = (poly-multiply (poly-multiply res res)
                                      (subseq poly 0 (min (length poly) (* 2 i))))
            for decr-len = (length decr)
            do (setq res (adjust-array res (* 2 i) :initial-element 0))
               (dotimes (j (* 2 i))
                 (setf (aref res j)
                       (mod (the ntt-int
                                 (+ (mod (* 2 (aref res j)) +ntt-mod+)
                                    (if (>= j decr-len) 0 (- +ntt-mod+ (aref decr j)))))
                            +ntt-mod+))))
      (adjust-array res result-length))))

(declaim (ftype (function * (values ntt-vector &optional)) poly-floor))
(defun poly-floor (poly1 poly2)
  (declare (optimize (speed 3))
           (vector poly1 poly2))
  (let* ((poly1 (coerce poly1 'ntt-vector))
         (poly2 (coerce poly2 'ntt-vector))
         (deg1 (+ 1 (or (position 0 poly1 :from-end t :test-not #'eql) -1)))
         (deg2 (+ 1 (or (position 0 poly2 :from-end t :test-not #'eql) -1))))
    (when (> deg2 deg1)
      (return-from poly-floor (make-array 0 :element-type 'ntt-int)))
    (setq poly1 (nreverse (subseq poly1 0 deg1))
          poly2 (nreverse (subseq poly2 0 deg2)))
    (let* ((res-len (+ 1 (- deg1 deg2)))
           (res (adjust-array (poly-multiply poly1 (poly-inverse poly2 res-len))
                              res-len)))
      (nreverse res))))

(declaim (ftype (function * (values ntt-vector &optional)) poly-sub))
(defun poly-sub (poly1 poly2)
  (declare (optimize (speed 3))
           (vector poly1 poly2))
  (let* ((poly1 (coerce poly1 'ntt-vector))
         (poly2 (coerce poly2 'ntt-vector))
         (len (max (length poly1) (length poly2)))
         (res (make-array len :element-type 'ntt-int :initial-element 0)))
    (replace res poly1)
    (dotimes (i (length poly2))
      (let ((value (+ (aref res i)
                      (the ntt-int (- +ntt-mod+ (aref poly2 i))))))
        (setf (aref res i)
              (if (>= value +ntt-mod+)
                  (- value +ntt-mod+)
                  value))))
    res))

(declaim (ftype (function * (values ntt-vector &optional)) poly-add))
(defun poly-add (poly1 poly2)
  (declare (optimize (speed 3))
           (vector poly1 poly2))
  (let* ((poly1 (coerce poly1 'ntt-vector))
         (poly2 (coerce poly2 'ntt-vector))
         (len (max (length poly1) (length poly2)))
         (res (make-array len :element-type 'ntt-int :initial-element 0)))
    (replace res poly1)
    (dotimes (i (length poly2))
      (let ((value (+ (aref res i) (aref poly2 i))))
        (setf (aref res i)
              (if (>= value +ntt-mod+)
                  (- value +ntt-mod+)
                  value))))
    res))

(declaim (ftype (function * (values ntt-vector &optional)) poly-mod))
(defun poly-mod (poly1 poly2)
  (declare (optimize (speed 3))
           (vector poly1 poly2))
  (let ((poly1 (coerce poly1 'ntt-vector))
        (poly2 (coerce poly2 'ntt-vector)))
    (when (loop for x across poly1 always (zerop x))
      (return-from poly-mod (make-array 0 :element-type 'ntt-int)))
    (let* ((res (poly-sub poly1 (poly-multiply (poly-floor poly1 poly2) poly2)))
           (end (+ 1 (or (position 0 res :from-end t :test-not #'eql) -1))))
      (subseq res 0 end))))

(declaim (ftype (function * (values ntt-vector &optional)) poly-total-prod))
(defun poly-total-prod (polys)
  "Returns the total polynomial product: polys[0] * polys[1] * ... * polys[n-1]."
  (declare (vector polys))
  (let* ((n (length polys))
         (dp (make-array n :element-type t)))
    (declare ((mod #.array-total-size-limit) n))
    (when (zerop n)
      (return-from poly-total-prod (make-array 1 :element-type 'ntt-int :initial-element 1)))
    (replace dp polys)
    (loop for width of-type (mod #.array-total-size-limit) = 1 then (ash width 1)
          while (< width n)
          do (loop for i of-type (mod #.array-total-size-limit) from 0 by (* width 2)
                   while (< (+ i width) n)
                   do (setf (aref dp i)
                            (poly-multiply (aref dp i) (aref dp (+ i width))))))
    (coerce (aref dp 0) 'ntt-vector)))

(declaim (ftype (function * (values ntt-vector &optional)) multipoint-eval))
(defun multipoint-eval (poly points)
  (declare (optimize (speed 3))
           (vector poly points)
           #+sbcl (sb-ext:muffle-conditions style-warning))
  (check-ntt-vector points)
  (let* ((poly (coerce poly 'ntt-vector))
         (points (coerce points 'ntt-vector))
         (len (length points))
         (table (make-array (max 0 (- (* 2 len) 1)) :element-type 'ntt-vector))
         (res (make-array len :element-type 'ntt-int)))
    (unless (zerop len)
      (sb-int:named-let %build ((l 0) (r len) (pos 0))
        (declare ((integer 0 #.most-positive-fixnum) l r pos))
        (if (= (- r l) 1)
            (let ((lin (make-array 2 :element-type 'ntt-int)))
              (setf (aref lin 0) (- +ntt-mod+ (aref points l)) ;; NOTE: non-zero
                    (aref lin 1) 1)
              (setf (aref table pos) lin))
            (let ((mid (ash (+ l r) -1)))
              (%build l mid (+ 1 (* pos 2)))
              (%build mid r (+ 2 (* pos 2)))
              (setf (aref table pos)
                    (poly-multiply (aref table (+ 1 (* pos 2)))
                                   (aref table (+ 2 (* pos 2))))))))
      (sb-int:named-let %eval ((poly poly) (l 0) (r len) (pos 0))
        (declare ((integer 0 #.most-positive-fixnum) l r pos))
        (if (= (- r l) 1)
            (let ((tmp (poly-mod poly (aref table pos))))
              (setf (aref res l) (if (zerop (length tmp)) 0 (aref tmp 0))))
            (let ((mid (ash (+ l r) -1)))
              (%eval (poly-mod poly (aref table (+ (* 2 pos) 1))) l mid (+ (* 2 pos) 1))
              (%eval (poly-mod poly (aref table (+ (* 2 pos) 2))) mid r (+ (* 2 pos) 2))))))
    res))

(defpackage :cp/mod-inverse
  (:use :cl)
  (:export #:mod-inverse))
(in-package :cp/mod-inverse)

;; TODO: signal DIVISION-BY-ZERO for non-coprime input when safety >= 1
(declaim (inline mod-inverse)
         (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 ((integer 1 #.most-positive-fixnum) modulus))
  (let ((a (mod a modulus))
        (b modulus)
        (u 1)
        (v 0))
    (declare (fixnum a b u v))
    (loop until (zerop b)
          for quot = (floor a b)
          do (decf a (the fixnum (* quot b)))
             (rotatef a b)
             (decf u (the fixnum (* quot v)))
             (rotatef u v))
    (mod u modulus)))

(defpackage :cp/mod-power-table
  (:use :cl)
  (:export #:make-mod-power-table))
(in-package :cp/mod-power-table)

(declaim (inline make-mod-power-table))
(defun make-mod-power-table (base length modulus &optional (element-type '(unsigned-byte 31)))
  "Returns a vector of the given length: VECTOR[x] := BASE^x mod MODULUS."
  (declare (fixnum base)
           ((integer 0 #.most-positive-fixnum) length)
           ((integer 1 #.most-positive-fixnum) modulus))
  (let ((res (make-array length :element-type element-type)))
    (unless (zerop length)
      (setf (aref res 0) 1)
      (loop for i from 1 below length
            do (setf (aref res i)
                     (mod (* base (aref res (- i 1))) modulus))))
    res))

;;;
;;; Binary heap
;;;

(defpackage :cp/abstract-heap
  (:use :cl)
  (:export #:heap-empty-error #:define-binary-heap))
(in-package :cp/abstract-heap)

(define-condition heap-empty-error (error)
  ((heap :initarg :heap :reader heap-empty-error-heap))
  (:report
   (lambda (condition stream)
     (format stream "Attempted to pop empty heap ~W" (heap-empty-error-heap condition)))))

(defmacro define-binary-heap (name &key order (element-type 'fixnum))
  "Defines a binary heap specialized for the given order and the element
type. This macro defines a structure of the given NAME and relevant functions:
MAKE-<NAME>, <NAME>-PUSH, <NAME>-POP, <NAME>-CLEAR, <NAME>-EMPTY-P,
<NAME>-COUNT, and <NAME>-PEEK.

If ORDER is not given, heap for dynamic order is defined instead: -PUSH and -POP
functions take order as an argument."
  (check-type name symbol)
  (let* ((string-name (string name))
         (fname-push (intern (format nil "~A-PUSH" string-name)))
         (fname-pop (intern (format nil "~A-POP" string-name)))
         (fname-clear (intern (format nil "~A-CLEAR" string-name)))
         (fname-empty-p (intern (format nil "~A-EMPTY-P" string-name)))
         (fname-count (intern (format nil "~A-COUNT" string-name)))
         (fname-peek (intern (format nil "~A-PEEK" string-name)))
         (fname-make (intern (format nil "MAKE-~A" string-name)))
         (acc-position (intern (format nil "~A-POSITION" string-name)))
         (acc-data (intern (format nil "~A-DATA" string-name)))
         (order (or order 'order)))
    `(progn
       (locally
           ;; prevent style warnings
           (declare #+sbcl (sb-ext:muffle-conditions style-warning))
         (defstruct (,name
                     (:constructor ,fname-make
                         (size
                          &aux
                          (data (make-array (1+ size)
                                            :element-type ',(if (eql element-type '*) t  element-type))))))
           (data nil :type (simple-array ,element-type (*)))
           (position 1 :type (integer 1 #.array-total-size-limit))))

       (declaim #+sbcl (sb-ext:maybe-inline ,fname-push))
       (defun ,fname-push (obj heap ,@(when (eql order 'order) '(order)))
         "Adds OBJ to HEAP."
         (declare (optimize (speed 3))
                  (type ,name heap))
         (symbol-macrolet ((position (,acc-position heap)))
           (when (>= position (length (,acc-data heap)))
             (setf (,acc-data heap)
                   (adjust-array (,acc-data heap)
                                 (min (- array-total-size-limit 1)
                                      (* position 2)))))
           (let ((data (,acc-data heap)))
             (declare ((simple-array ,element-type (*)) data))
             (labels ((heapify (pos)
                        (declare (optimize (speed 3) (safety 0)))
                        (unless (= pos 1)
                          (let ((parent-pos (ash pos -1)))
                            (when (funcall ,order (aref data pos) (aref data parent-pos))
                              (rotatef (aref data pos) (aref data parent-pos))
                              (heapify parent-pos))))))
               (setf (aref data position) obj)
               (heapify position)
               (incf position)
               heap))))

       (declaim #+sbcl (sb-ext:maybe-inline ,fname-pop))
       (defun ,fname-pop (heap ,@(when (eql order 'order) '(order)))
         "Removes and returns the element at the top of HEAP."
         (declare (optimize (speed 3))
                  (type ,name heap))
         (symbol-macrolet ((position (,acc-position heap)))
           (let ((data (,acc-data heap)))
             (declare ((simple-array ,element-type (*)) data))
             (labels ((heapify (pos)
                        (declare (optimize (speed 3) (safety 0))
                                 ((integer 1 #.array-total-size-limit) pos))
                        (let* ((child-pos1 (+ pos pos))
                               (child-pos2 (1+ child-pos1)))
                          (when (<= child-pos1 position)
                            (if (<= child-pos2 position)
                                (if (funcall ,order (aref data child-pos1) (aref data child-pos2))
                                    (unless (funcall ,order (aref data pos) (aref data child-pos1))
                                      (rotatef (aref data pos) (aref data child-pos1))
                                      (heapify child-pos1))
                                    (unless (funcall ,order (aref data pos) (aref data child-pos2))
                                      (rotatef (aref data pos) (aref data child-pos2))
                                      (heapify child-pos2)))
                                (unless (funcall ,order (aref data pos) (aref data child-pos1))
                                  (rotatef (aref data pos) (aref data child-pos1))))))))
               (when (= position 1)
                 (error 'heap-empty-error :heap heap))
               (prog1 (aref data 1)
                 (decf position)
                 (setf (aref data 1) (aref data position))
                 (heapify 1))))))

       (declaim (inline ,fname-clear))
       (defun ,fname-clear (heap)
         "Makes HEAP empty."
         (setf (,acc-position heap) 1)
         heap)

       (declaim (inline ,fname-empty-p))
       (defun ,fname-empty-p (heap)
         "Returns true iff HEAP is empty."
         (= 1 (,acc-position heap)))

       (declaim (inline ,fname-count))
       (defun ,fname-count (heap)
         "Returns the current number of the elements in HEAP."
         (- (,acc-position heap) 1))

       (declaim (inline ,fname-peek))
       (defun ,fname-peek (heap)
         "Returns the topmost element of HEAP. Signals HEAP-EMPTY-ERROR if HEAP
is empty."
         (if (= 1 (,acc-position heap))
             (error 'heap-empty-error :heap heap)
             (aref (,acc-data heap) 1))))))

#+(or)
(define-binary-heap heap
  :order #'>
  :element-type fixnum)

;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/abstract-heap :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/mod-power-table :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/mod-inverse :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/polynomial-ntt :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/read-fixnum :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/ntt :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/binomial-coefficient-mod :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/mod-operations :cl-user))
(in-package :cl-user)

;;;
;;; Body
;;;

(define-binary-heap heap
  :order (lambda (poly1 poly2)
           (< (length poly1) (length poly2)))
  :element-type ntt-vector)

(defun main ()
  (let* ((n (read))
         (hcounter (make-array 100000 :element-type 'uint31 :initial-element 0))
         (powers (make-mod-power-table 499122177 100001 +mod+))
         (fs (make-array (+ n 1) :element-type 'uint31 :initial-element 0)))
    (declare (uint31 n))
    (dotimes (i (* 2 n))
      (incf (aref hcounter (- (read-fixnum) 1))))
    (dotimes (i (+ n 1))
      (setf (aref fs i) (mod* (aref *fact* (* 2 i))
                              (aref powers i)
                              (aref *fact-inv* i))))
    (let* ((hcounter (delete 0 hcounter))
           (que (make-heap n)))
      (dotimes (j (length hcounter))
        (let* ((k (aref hcounter j))
               (poly (make-array (+ 1 (floor k 2)) :element-type 'uint31)))
          (loop for i from 0 below (length poly)
                do (setf (aref poly i)
                         (mod* (binom k (* 2 i)) (aref fs i))))
          (dbg k poly)
          (heap-push poly que)))
      (loop while (>= (heap-count que) 2)
            for poly1 = (heap-pop que)
            for poly2 = (heap-pop que)
            do (heap-push (poly-multiply poly1 poly2) que))
      (let ((poly (heap-pop que))
            (res 0))
        #>poly
        (loop for i from 0 below (length poly)
              for sign = 1 then (* sign -1)
              ;; while (<= (* 2 i) n)
              do (incfmod res (mod* (aref poly i) (aref fs (- n i)) sign)))
        (println res)))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(progn
  (defparameter *lisp-file-pathname* (uiop:current-lisp-file-pathname))
  (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *lisp-file-pathname*))
  (defparameter *problem-url* "https://atcoder.jp/contests/abl/tasks/abl_f"))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

#-swank
(eval-when (:compile-toplevel)
  (when (or (> sb-c::*compiler-warning-count* 0)
            sb-c::*undefined-warnings*)
    (error "count: ~D, undefined warnings: ~A"
           sb-c::*compiler-warning-count*
           sb-c::*undefined-warnings*)))

;; To run: (5am:run! :sample)
#+swank
(5am:test :sample
  (5am:is
   (equal "2
"
          (run "2
1
1
2
3
" nil)))
  (5am:is
   (equal "516
"
          (run "5
30
10
20
40
20
10
10
30
50
60
" nil))))


Measured memory_bytes: 47752