Yêu cầu

DatVilla định nghĩa một từ là “một chuỗi chỉ bao gồm ‘o’ hoặc ‘x’” và yêu cầu bổ sung: đối với mỗi chuỗi con có độ dài là số nguyên tố, số lượng ‘o’ không nhỏ hơn số lượng ‘x’.

DatVilla cho bạn một số N (\(1 \le N \le 10^{12}\)). DatVilla đố bạn tính được có bao nhiêu từ có thể được tạo ra với độ dài chính xác N, kết quả lấy modulo 1 000 000 007.

Dữ liệu vào Specification

• Một dòng chứa số N.

Dữ liệu ra Specification

• Ghi ra kết quả bài toán.

Sample Input

    2

Sample Output

    3

Giải thích

Các từ có thể tạo ra là: “oo”, “ox”, “xo”.