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