Phân tích số

Trong một ngôi làng tuyệt đẹp nằm giữa những ngọn núi xanh mướt, có một vị thủ lĩnh hiền lành tên là H, người sẽ đặt ra một nhiệm vụ khó khăn cho dân làng.

Vị thủ lĩnh H yêu cầu tất cả mọi người tạo ra các dãy số nguyên dương có tổng bằng $S$. Nhưng không chỉ đơn giản là tạo ra bất kỳ dãy số nào, mà các dãy này phải có một đặc điểm đặc biệt, đó là ước số chung lớn nhất của tất cả các số trong dãy phải bằng $1$.

Dân làng đã nhận nhiệm vụ này, họ bắt đầu suy nghĩ và tạo ra nhiều dãy số khác nhau và ước số chung lớn nhất của tất cả các phần tử trong dãy luôn là $1$. Mỗi người đều có những cách riêng để tạo ra các dãy số này. Tuy nhiên, họ không thể xác định được có tất cả bao nhiêu dãy số thỏa mãn theo yêu cầu của vị thủ lĩnh.

Yêu cầu: Bạn hãy giúp dân làng xác định được số lượng các dãy số có tổng bằng $S$ mà ước số chung lớn nhất của tất cả các phần tử trong dãy bằng $1$.

Một dãy có thể gồm một hoặc nhiều phần tử (dãy chỉ có một phần tử $a$ có ước chung lớn nhất là $a$). Hai dãy khác nhau nếu khác độ dài hoặc khác nhau ở ít nhất một vị trí, nên các dãy chỉ khác thứ tự phần tử được tính riêng.

Ví dụ với $S=3$, ta có $3$ dãy: $(1,1,1)$, $(1,2)$, $(2,1)$.

Dữ liệu vào

Một số nguyên dương $S$ ($S\le {10}^9$).

Dữ liệu ra

Một số nguyên duy nhất là số dư của kết quả tìm được khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le S\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $S\le 20$.
• Subtask 2 ($30\%$ số điểm): $S\le {10}^6$.
• Subtask 3 ($40\%$ số điểm): $S\le {10}^9$.

Mỗi subtask được chấm theo nhóm: chỉ được điểm của subtask khi đúng mọi test thuộc subtask đó.

Ví dụ