Background

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

输出的答案对$10^9+7$取模。

Input

共一行，包含整数$n$。

Output

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

Samples

3

5

Limitation

$1≤n≤10^5$