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

(declaim (inline power-mod))
(defun power-mod (base power &optional (divisor 1000000007))
  "BASE := integer
POWER, DIVISOR := non-negative fixnum"
  (declare ((integer 0 #.most-positive-fixnum) divisor)
           (integer base))
  (labels ((recur (x p)
             (cond ((zerop p) 1)
                   ((evenp p) (recur (mod (* x x) divisor) (ash p -1)))
                   (t (mod (* x (recur x (- p 1))) divisor)))))
    (declare (ftype (function ((unsigned-byte 32) (integer 0 #.most-positive-fixnum))
                              (values (integer 0 #.most-positive-fixnum) &optional))
                    recur))
    (recur (mod base divisor) power)))
(declaim (notinline power-mod))

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

(defconstant +binom-size+ 210000)
(defconstant +binom-mod+ #.(+ (expt 10 9) 7))

(declaim ((simple-array (unsigned-byte 32) (*)) *fact* *fact-inv* *inv*))
(defparameter *fact* (make-array +binom-size+ :element-type '(unsigned-byte 32)))
(defparameter *fact-inv* (make-array +binom-size+ :element-type '(unsigned-byte 32)))
(defparameter *inv* (make-array +binom-size+ :element-type '(unsigned-byte 32)))

(defun initialize-binom ()
  (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) (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+)))

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

;; TODO: deal with bignums
(declaim (inline ext-gcd))
(defun ext-gcd (a b)
  "Returns two integers X and Y where AX + BY = gcd(A, B) holds."
  (declare (fixnum a b))
  (labels ((%gcd (a b)
             (declare (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))))))))))
    (if (>= a 0)
        (if (>= b 0)
            (%gcd a b)
            (multiple-value-bind (x y) (%gcd a (- b))
              (declare (fixnum x y))
              (values x (- y))))
        (if (>= b 0)
            (multiple-value-bind (x y) (%gcd (- a) b)
              (declare (fixnum x y))
              (values (- x) y))
            (multiple-value-bind (x y) (%gcd (- a) (- b))
              (declare (fixnum x y))
              (values (- x) (- y)))))))

(defun mod-inverse (a m)
  "Solves ax ≡ 1 mod m. A and M must be coprime."
  (declare (integer a)
           ((integer 1 #.most-positive-fixnum) m))
  (mod (ext-gcd (mod a m) m) m))

(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
(defun mod* (&rest args)
  (reduce (lambda (x y) (mod (* x y) +mod+)) args))

(define-compiler-macro mod* (&rest args)
  (if (null args)
      1
      (reduce (lambda (x y) `(mod (* ,x ,y) +mod+)) args)))

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

(define-compiler-macro mod+ (&rest args)
  (if (null args)
      0
      (reduce (lambda (x y) `(mod (+ ,x ,y) +mod+)) args)))

(define-modify-macro incfmod (delta divisor)
  (lambda (x y divisor) (mod (+ x y) divisor)))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (a (read))
         (b (read))
         (a+b^-1 (mod-inverse (+ a b) +mod+))
         (c (read))
         (a^n (power-mod a n +mod+))
         (b^n (power-mod b n +mod+))
         (res 0))
    (declare ((integer 0 100) a b c)
             (uint32 n res a+b^-1)
             (ignore c))
    (locally (declare (inline power-mod))
      (loop for m from n to (- (* 2 n) 1)
            do (incfmod res
                        (mod* m
                              (binom (- m 1) (- n 1))
                              (mod+ (mod* a^n (power-mod b (- m n) +mod+))
                                    (mod* b^n (power-mod a (- m n) +mod+)))
                              (power-mod a+b^-1 m +mod+))
                        +mod+)))
    (println (mod* res 100 a+b^-1))))

#-swank(main)


Measured memory_bytes: 44900