Cho một sàn gạch có kích thước \(2*N\) và \(N\) loại gạch kích thước \(1*i\) với loại thứ \(i\). Sử dụng vô hạn viên gạch mỗi loại, hãy tìm cách lát sàn sao cho mỗi viên gạch chỉ có thể nằm ngang hoặc nằm dọc, không có miếng gạch nào đè lên nhau và phải vừa hoàn toàn với sàn (không thừa ra ngoài).

Biết không thể cắt miếng gạch nào, hãy đếm xem có bao nhiêu cách lát sàn khác nhau thoả mãn.

Ví dụ một cách lát sàn \(2*2\) thoả mãn :

Vì kết quả có thể rất lớn, hãy in ra dư của kết quả sau khi chia cho \(10^9+6\)

Input

• Dòng duy nhất chứa số nguyên dương \(N\).
• \(N\le 10^{18}\)

Output

• Dòng duy nhất chứa dư của số cách để lát gạch khi chia cho \(10^9+6\).

Example

2

7

Đừng hỏi tại sao author cho MOD là hợp số.