Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Hôm nay là một ngày se se lạnh nên H quyết định rủ T đi ăn King BBQ. Nhưng khi đến quán King BBQ thi T và H thấy một bài toán về hoán vị như sau.

Cho 1 số nguyên dương n. Xem xét tất cả hoán vị từ 1 đến n theo thứ tự từ điển và ghép chúng thành một chuỗi p. Độ dài của chuỗi p này sẽ là n ⋅ n!.

Ví dụ n = 3 thì p = [1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1].

Cho 1 ≤ i ≤ j ≤  n ⋅ n! là một cặp chỉ số. Nhà hàng King BBQ gọi đoạn (p_i, p_i+1, …, p_j−1, p_j) có độ dài của chuỗi con này được định nghĩa là số phần tử của p (nghĩa là j – i + 1 = n) là Gr. Nhà hàng King BBQ yêu cầu tìm số lượng chuỗi con là Gr thỏa mãn có chiều dài là n và có tổng là n * (n - 1)/2 . Nếu tìm chính xác sẽ nhận được phiếu giảm giá 19% mỗi lần đến ăn trong 5 tháng liên tiếp.

Nhiệm vụ của bạn là hãy tìm số chuỗi Gr thỏa mãn yêu cầu của nhà hàng. Lưu ý số chuỗi Gr thỏa mãn là rất lớn nên bạn hãy lấy dư cho 10⁹ + 7.

Input

• Dòng duy nhất chứ số nguyên dương n (1 ≤ n ≤ 10⁶).

Output

• Xuất ra 1 số nguyên duy nhất là kết quả cần tìm lấy dư cho 10⁹ + 7.

Example

Input
3

Output
9

Giải thích:

Trong ví dụ đầu tiên có 16 chuỗi con Gr có độ dài là 3. Theo thứ tự xuất hiện của chúng là:

[1,2,3], [1,2,3], [2,3,1], [2,3,1], [3,1,3], [3,1,3], [1,3,2], [1,3,2], [3,2,2], [3,2,2], [2,2,1], [2,2,1], [2,1,3], [2,1,3], [1,3,2], [1,3,2], [3,2,3], [3,2,3], [2,3,1], [2,3,1], [3,1,3], [3,1,3], [1,3,1], [1,3,1], [3,1,2], [3,1,2], [1,2,3], [1,2,3], [2,3,2], [2,3,2], [3,2,1], [3,2,1].

Có tổng lần lượt là 6, 6, 7, 6, 7, 5, 6, 6, 8, 6, 7, 5, 6, 6, 7, 6. Với tổng bằng 6 thì có 9 chuỗi Gr thoả mãn.