(defconstant +mod+ 1000000007) (defun %mod-inverse (a_ m_) (let ((a a_) (m m_) (b m_) (u 1) (v 0)) (loop while (plusp b) do (let ((s (floor a b))) (decf a (* s b)) (rotatef a b) (decf u (* s v)) (rotatef u v))) (mod u m))) (defvar *mod-fact* (make-array 1000001 :element-type 'integer)) (defvar *mod-fact-inv* (make-array 1000001 :element-type 'integer)) (defvar *mod-inv* (make-array 1000001 :element-type 'integer)) (defun %init-mod-combination (n m) (setf (aref *mod-fact* 0) 1 (aref *mod-fact-inv* n) 1 (aref *mod-inv* 0) 1) (loop for i from 1 to n do (setf (aref *mod-fact* i) (mod (* i (aref *mod-fact* (1- i))) m))) (setf (aref *mod-fact-inv* n) (%mod-inverse (aref *mod-fact* n) m)) (loop for i from (1- n) downto 0 do (setf (aref *mod-fact-inv* i) (mod (* (aref *mod-fact-inv* (1+ i)) (1+ i)) m))) (loop for i from 1 to n do (setf (aref *mod-inv* i) (mod (* (aref *mod-fact* (1- i)) (aref *mod-fact-inv* i)) m)))) (defun %mod-nCk (n k m) (if (or (minusp k) (< n k)) 0 (mod (* (aref *mod-fact* n) (aref *mod-fact-inv* k) (aref *mod-fact-inv* (- n k))) m))) (defun %mod-nPk (n k m) (if (or (minusp k) (< n k)) 0 (mod (* (aref *mod-fact* n) (aref *mod-fact-inv* (- n k))) m))) (defun %mod-nHk (n k m) (if (= n k 0) 1 (%mod-nCk (+ n k -1) k m))) (defun main (&rest argv) (declare (ignorable argv)) (%init-mod-combination 500001 +mod+) (let* ((n (read)) (res 0) (k 0)) (loop for i from (1- n) below (* 2 n) by 2 do (let ((x (%mod-nCk i (+ n k -1) +mod+)) (y (%mod-nCk i (+ n k) +mod+))) (incf k) (setq res (mod (+ res x (- y)) +mod+)))) (format t "~d~%" res))) (main)