Cho đoạn mã C++ sau đây:

int random(int L, int R) {
    // return a random value in range [L, R] with an equal probability
}

int call(int l, int r) {
    if (r - l <= 1) return 0;
    int idx = random(l, r);
    if (idx == l || idx == r) return 1 + call(l, r);
    return 1 + call(l, idx - 1) + call(idx + 1, r);
}

Hãy tính Giá trị kì vọng của hàm call(1, n), với ~n~ là dữ liệu nhập vào.

Input

• Một dòng duy nhất chứa số nguyên dương ~n~ (~1 \le n \le 10^6~).

Output

• Biết đáp án của bài toán sẽ có dạng phân số tối giản ~\frac{p}{q}~, hãy in ra ~p \times q^{-1} \mod 10^9 + 7~.

Scoring

• ~40\%~ số test thỏa mãn ~n \le 500~.

• ~40\%~ số test khác thỏa mãn ~n \le 5000~.

• ~20\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3

Sample Output 1

3