题目描述

给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。

输出的答案对 109+7 取模。

输入格式

共一行，包含整数 n。

1≤n≤1e5

输出格式

共一行，包含一个整数，表示答案。

样例

3

5

提示

by 陈代睿（有问题在群里@我）

对于样例，只有一下五种情况：

0 0 0 1 1 1

0 0 1 1 0 1

0 0 1 0 1 1

0 1 0 0 1 1

0 1 0 1 0 1