CQXYM считает перестановки длины \(2n\).
Перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Перестановка \(p\)(длины \(2n\)) будет посчитана только в том случае, если количество \(i\), удовлетворяющих \(p_i<p_{i+1}\), не меньше \(n\). Например:
- Перестановка \([1, 2, 3, 4]\) будет посчитана, так как количество таких \(i\) что \(p_i<p_{i+1}\) равно \(3\) (\(i = 1\), \(i = 2\), \(i = 3\)).
- Перестановка \([3, 2, 1, 4]\) не будет посчитана, так как количество таких \(i\) что \(p_i<p_{i+1}\) равно \(1\) (\(i = 3\)).
CQXYM хочет, чтобы вы помогли ему найти количество таких перестановок по модулю \(1000000007\)(\(10^9+7\)).
Операцией по модулю называется взятие остатка от деления. Например:
- \(7 \mod 3=1\), так как \(7 = 3 \cdot 2 + 1\),
- \(15 \mod 4=3\), так как \(15 = 4 \cdot 3 + 3\).
Примечание
\(n=1\), существует только одна перестановка, удовлетворяющая условию: \([1,2].\)
В перестановке \([1,2]\), \(p_1<p_2\), только \(i=1\) подходит под условие. Так как \(1 \geq n\), Эта перестановка будет посчитана. В перестановке \([2,1]\), \(p_1>p_2\). Так как \(0<n\), эта перестановка не будет посчитана.
\(n=2\), существует \(12\) перестановок: \([1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,1,3],[3,1,2,4],[3,4,1,2],[4,1,2,3].\)