Cho số nguyên dương \(N\).

Xét tổng \(S_N=\sum_{k=1}^{N}\frac{1}{k(k+1)}\left(1+\frac{1}{k^2+k+1}\right)\).

Yêu cầu tính chính xác \(F(N)=\prod_{k=1}^{N}\left(1+\frac{2k+1}{k(k+1)(k^2+k+1)}\right)\).

Kết quả được viết dưới dạng phân số tối giản \(F(N)=\frac{P}{Q}\) \((\gcd(P,Q)=1)\).

Tính \(P\times Q^{-1}\pmod {1000000007}\).

Input

• Một dòng duy nhất chứa bốn số nguyên dương: \(N\) \((1 \le N \le 10^{100000})\)

Output

• In ra một số nguyên duy nhất \(P\times Q^{-1}\pmod {1000000007}\)

Example

36

540540557