#O1093. 出栈序列计数

出栈序列计数

题目描述

把 1,2,⋯ ,n1,2,\cdots,n 依次压入栈,过程中可以随时弹出元素,最终全部弹出。问能得到多少种不同的出栈序列。答案对 109+710^9+7 取模。

输入格式

一行一个整数 nn。

输出格式

一行一个整数,表示方案数模 109+710^9+7。

样例 #1

样例输入 #1

3

样例输出 #1

5

数据规模与约定

数据范围 说明
1≤n≤30001 \le n \le 3000 元素个数
  • 答案是第 nn 个卡特兰数 1n+1(2nn)\dfrac{1}{n+1}\binom{2n}{n}。