#P1478. 2023.08.22-PDD服务端研发笔试-第二题-塔子哥的01排列

2023.08.22-PDD服务端研发笔试-第二题-塔子哥的01排列

题目内容

塔子哥有 nn 个数字 00 和 nn 个数字 11 。

现在，塔子哥要从这 2n2n 个数字中选出 nn 个数字进行排列。

但是对塔子哥来说，排列中连续出现两个 00 是让他不能接受的。

现在，塔子哥想问你，可以选出多少种不同的排列方式。

输入描述

一行，一个整数 n(1≤n≤5×106)n(1\leq n\leq 5\times 10^6) 表示有 nn 个数字 00 和 nn 个数字 11 。

输出描述

输出不同排列的方案数，答案对 109+710^9 + 7 取模。

样例

输入

2

输出

3

说明 00 不符合塔子哥的要求，01, 10, 11 都是符合要求的。共有 33 种。

知识点:*****

查看知识点以及同类型题目

Statistics