11604: 【原1604】Interesting Stack
题目
题目描述
author: xzj 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1604
Description
将1-N按顺序入栈，且可以在任意“栈非空的时刻”弹出栈顶元素，以此种方法得到的出栈序列（弹出的栈顶元素依次组成的序列）即为合法的出栈序列。两个出栈序列是不同的，当且仅当两个序列中存在至少一位不相同的元素。
定义一个出栈序列的代价为cost，则cost为“每次有元素入栈时，将全部栈内元素的标号求和”的和。例如，当n=4时，某个操作序列为“1入 2入 2出 3入 3出 1出 4入 4出”，则有“1入时cost+=1，2入时cost+=(1+2)，3入时cost+=(1+3)，4入时cost+=4”。
求全部不同的合法出栈序列的cost的和，答案对1000000007（10^9+7）取模。
Input Format
一个整数 N。
Output Format
一个数 ANS % 1000000007。
Sample Input
2
Sample Output
7
Hint
共有两种方案：
1入1出2入2出（答案为1+2）
1入2入2出1出（答案为1+3）
Limits
- 对于30%的数据，n不超过12；
- 对于60%的数据，n不超过22；
- 对于100%的数据，n不超过100.
- （对于所有的数据，n各不相同。保证有小数据，你懂的）
Another Hint
如果AK了，可以考虑一下n=1000时的做法。
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！