Chán cuộc sống nông trại, đàn bò đã bán hết mọi tài sản trần thế và gia nhập đoàn của một gánh xiếc lưu động. Cho đến nay, đàn bò chỉ được giao những tiết mục dễ dàng: tung hứng đuốc, đi dây, cưỡi xe một bánh — không có gì mà một cô bò khéo móng lại không xử lý được. Tuy nhiên, người quản lý gánh xiếc muốn tạo ra một tiết mục kịch tính hơn nhiều cho buổi diễn tiếp theo.

Sân khấu cho tiết mục mới gồm \(N\) bục được xếp thành một vòng tròn. Trên mỗi bục, từ \(1\) đến \(N\) cô bò phải xếp thành một chồng, cô nọ đứng trên cô kia. Khi người quản lý ra hiệu, tất cả các chồng phải đồng thời đổ theo chiều kim đồng hồ: cô bò dưới cùng trong một chồng không di chuyển, cô bò phía trên cô ấy di chuyển một bục theo chiều kim đồng hồ, cô bò tiếp theo di chuyển hai bục theo chiều kim đồng hồ, và cứ tiếp tục như vậy. Vì là những vận động viên thể dục điêu luyện, đàn bò biết rằng chúng sẽ không gặp khó khăn với khía cạnh kỹ thuật của tiết mục này. Các chồng bò khác nhau sẽ không “cản trở” nhau khi đổ, nên mọi cô bò đều sẽ đáp xuống bục dự định. Tất cả các cô bò đáp xuống cùng một bục tạo thành một chồng mới và chồng này không đổ tiếp.

Người quản lý cho rằng tiết mục sẽ đặc biệt kịch tính nếu sau khi các chồng đổ, chồng mới trên mỗi bục chứa đúng bằng số bò trong chồng ban đầu trên bục đó. Ta gọi một cấu hình kích thước các chồng là “kỳ diệu” nếu nó thỏa mãn điều kiện này. Hãy giúp đàn bò tính số cấu hình kỳ diệu. Vì số này có thể rất lớn, hãy tính phần dư của nó khi chia cho \(10^9 + 7\).

Hai cấu hình được xem là khác nhau nếu tồn tại bất kỳ bục nào mà hai cấu hình gán số bò khác nhau.

Dữ liệu vào

Dữ liệu vào gồm một số nguyên duy nhất \(N\) (\(1 \leq N \leq 10^{12}\)).

Dữ liệu ra

In ra một số nguyên duy nhất là số cấu hình kỳ diệu modulo \(10^9 + 7\).

Ví dụ

4

6

Nguồn

USACO 2018 February Contest, Platinum — Cow Gymnasts

Tác giả bài toán: Dhruv Rohatgi.