Tèo quên mất \(K\) ký tự cuối của mật khẩu đăng nhập website học trực tuyến của mình, bạn ấy chỉ nhớ rằng những ký tự này chỉ được đặt bởi các chữ số 0, chữ số 1 và chữ số 2 nhưng không có hai chữ số liên tiếp giống nhau và không có hai chữ số 0 và 1 đứng liền nhau.

Input

• Dữ liệu vào gồm một số nguyên \(K\) (\(2 \le K \le 10^9\)).

Output

• In ra một số nguyên duy nhất là số lần nhiều nhất để Tèo đoán được mật khẩu.

Note

• Nếu đáp án lớn hơn \(10^9\) thì chia lấy dư cho \(10^9 + 7\).

Example

2

4

3

6