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.

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~.

Ví dụ với ~S=3~, ta có ~3~ dãy:

1. ~(1,1,1)~

2. ~(1,2)~

3. ~(2,1)~

Input

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

Output

• 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~.

Scoring

Sample Input 1

5

Sample Output 1

15