;; -*- 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
(declaim (inline mod-factorial))
(defun mod-factorial (n modulus)
  "Returns N! mod MODULUS."
  (declare ((integer 0 #.most-positive-fixnum) n modulus))
  (labels ((recur (n result)
             (declare ((integer 0 #.most-positive-fixnum) n result))
             (if (zerop n)
                 result
                 (recur (- n 1) (mod (* result n) modulus)))))
    (recur n 1)))

(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
;;;
;;; Arithmetic operations with static modulus
;;;

(defmacro define-mod-operations (&optional (divisor 1000000007))
  `(progn
     (defun mod* (&rest args)
       (reduce (lambda (x y) (mod (* x y) ,divisor)) args))

     (sb-c:define-source-transform mod* (&rest args)
       (if (null args)
           1
           (reduce (lambda (x y) `(mod (* ,x ,y) ,',divisor)) args)))

     (defun mod+ (&rest args)
       (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)

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (s (read-line))
         (dirs (make-array (* 2 n) :element-type 'bit))
         (l-cumuls (make-array (+ (* 2 n) 1) :element-type 'uint32 :initial-element 0))
         (r-cumuls (make-array (+ (* 2 n) 1) :element-type 'uint32 :initial-element 0))
         (res 1))
    (declare (simple-string s)
             (uint31 n res))
    (unless (and (char= #\B (aref s 0) (aref s (- (* 2 n) 1))))
      (println 0)
      (return-from main))
    (loop for i from 1 below (* 2 n)
          do (if (char= (aref s i) (aref s (- i 1)))
                 (setf (aref dirs i) (logxor 1 (aref dirs (- i 1))))
                 (setf (aref dirs i) (aref dirs (- i 1)))))
    (dotimes (i (* 2 n))
      (setf (aref l-cumuls (+ i 1))
            (+ (aref l-cumuls i) (logxor 1 (aref dirs i))))
      (setf (aref r-cumuls (+ i 1))
            (+ (aref r-cumuls i) (aref dirs i))))
    (unless (and (= 0 (aref dirs 0))
                 (= 1 (aref dirs (- (* 2 n) 1)))
                 (= (count 0 dirs) (count 1 dirs)))
      (println 0)
      (return-from main))
    (dotimes (i (* 2 n))
      (when (= 1 (aref dirs i))
        (mulfmod res (max 0 (- (aref l-cumuls i) (aref r-cumuls i))))))
    (println (mod* (mod-factorial n +mod+) res))))

#-swank (main)


Measured memory_bytes: 33892