Problem Description

已知

$$ F(n) = \sum_{i=1}^n (i \times \sum_{j=i}^n C_j^i) $$

求 F(n) mod 1000000007

Input

多组输入，每组输入占一行，包含一个整数n（1 <= n <= 1e18)。
数据不超过300000组。

Output

对于每组输入，输出一行，包括一个数代表答案。

5
100

129
660756544