Lưới \(2 \times N\). Mỗi bước đi sang phải, lên hoặc xuống. Đếm số cách đi từ \((1,1)\) đến \((2,N)\). Modulo \(10^9+7\).

Định dạng đầu vào

• Một dòng chứa \(N\) (\(1 \le N \le 10^{18}\)).

Định dạng đầu ra

• Một số nguyên là kết quả.

Ví dụ

Input:

4

Output:

8

Ràng buộc

• 100% số điểm: \(N \le 10^{18}\).