(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defun displace (vec &optional (start 0) end)
  "displaced subseq"
  (let ((end (or end (length vec))))
    (make-array (- end start)
                :element-type (array-element-type vec)
                :displaced-to vec
                :displaced-index-offset start)))

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

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

(defconstant +mod+ 1000000007)

;; Hauptteil

(declaim (inline simple-base-string40=))
(defun simple-base-string40= (s1 s2)
  (declare #.OPT
           ((simple-base-string 40) s1 s2))
  (equal s1 s2))

(declaim (inline sxhash-sbs40))
(defun sxhash-sbs40 (string)
  (declare #.OPT
           ((simple-base-string 40) string))
  (macrolet ((set-result (form)
               `(setf result (ldb (byte 64 0) ,form))))
    (let ((result 0))
      (declare (uint64 result))
      (dotimes (i 5)
        (set-result (+ result (sb-kernel:%vector-raw-bits string i)))
        (set-result (logxor result (ash result -6))))
      (set-result (logxor result (ash result -11)))
      (logand result most-positive-fixnum))))

(sb-ext:define-hash-table-test simple-base-string40= sxhash-sbs40)

(declaim (inline extract))
(defun extract (mask s)
  (let* ((res (make-string 40 :element-type 'base-char :initial-element #\Nul)))
    (loop with red-i = 0
          with blue-i = 20
          for pos below (length s)
          do (if (logbitp pos mask)
                 (progn (setf (aref res red-i) (aref s pos))
                        (incf red-i))
                 (progn (setf (aref res  blue-i) (aref s pos))
                        (incf blue-i))))
    res))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (s (read-line))
         (s1 (coerce (reverse (displace s 0 n)) 'simple-base-string))
         (s2 (coerce (displace s n (+ n n)) 'simple-base-string))
         (table (make-hash-table :test #'simple-base-string40= :size #.(expt 2 18))))
    (declare ((integer 1 18) n))
    (dotimes (mask (expt 2 n))
      (let ((key (extract mask s1)))
        (multiple-value-bind (value presentp) (gethash key table)
          (if presentp
              (setf (gethash key table) (1+ (the uint32 value)))
              (setf (gethash key table) 1)))))
    (let ((res 0))
      (declare (fixnum res))
      (dotimes (mask (expt 2 n))
        (let* ((key (extract mask s2))
               (value (gethash key table)))
          (when value
            (incf res (the uint32 value)))))
      (println res))))

#-swank(main)


Measured memory_bytes: 74216