Siro có ~N~ viên bi xanh và ~N~ viên bi đỏ. Trong bảng ~2N + 1~ ô, Siro xếp ~N~ viên bi xanh liền nhau ở ~N~ ô đầu tiên, sau đó bỏ trống ~1~ ô ở giữa và xếp tiếp ~N~ viên bi đỏ vào ~N~ ô cuối cùng như hình ~a~.

Hiện tại, Siro muốn biết số lần chuyển ít nhất các viên bi sao cho thu được hình ~b~.

Lưu ý: Các viên bi xanh được chuyển sang trái ô trống, các viên bi đỏ được qua phải ô trống. Mỗi lần được phép chuyển một viên bi qua ô trống kề viên bi đó hoặc cách viên bi đó ~1~ ô.

Với ~N = 3~, ta được bảng sau:

Bạn hãy giúp Siro nhé!

Input

Gồm ~1~ dòng duy nhất chứa số nguyên dương ~N (1 \le N \le 10^9)~

Output

Gồm ~1~ dòng chứa duy nhất ~1~ số nguyên dương là kết quả của bài toán trên.

• Chú ý: Đáp án có thể rất lớn, hãy in ra đáp án sau khi chia dư cho ~10^9 + 7~

Sample

Input #1

1

Output #1

3

Hint

Với #1, ra có các bước chuyển sau:

~1.~ OBR

~2.~ RBO

~3.~ ROB

Chú ý:

• B là bi xanh
• R là bi đỏ
• O là ô trống