众所周知,小葱同学擅长计算,尤其擅长计算组合数,但这个题和组合数没什么关系。
现在我们有𝑁只皮克敏站成一排,每只皮克敏一开始等概率向左或者向右走,速度一样,遇见边界掉头(即最左边和最右边的皮克敏一开始的方向是无所谓的)。
如果两只皮克敏相遇,则体积大的会吃掉小的,体积变成两者之和;如果体积一样,则向左走的吃掉向右走的。现在问每一只皮克敏成为最后活下来的皮克敏的概率。
【输入格式】
一行一个整数𝑁。
【输出格式】
一行一个整数,如果第𝑖只皮克敏获胜的概率为𝑝𝑖的话,则输出($\sum^N_{i=1} 𝑝_𝑖 × 2^𝑁 × 𝑖) 𝑚𝑜𝑑 (10^9 + 7$)。
【样例输入】
5
【样例输出】
112
【数据规模与约定】
对于20%的数据,𝑁 ≤ 10。
对于40%的数据,𝑁 ≤ 50。
对于60%的数据,𝑁 ≤ 200。
对于80%的数据,𝑁 ≤ 5000。
对于100%的数据,𝑁 ≤ 10^6
时间限制:1 s
空间限制:256 MB