Mở khóa két sắt

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Dạng bài

Một ngày đẹp trời, Ban mua một chiếc két sắt khá đặc biệt, bên trên có n cái nút, các nút được đánh dấu từ 1 tới n.

Để mở được ổ khóa thì Ban phải ấn n nút đó theo 1 thứ tự nhất định. Nếu nhấn 1 nút chính xác thì các nút khác và nút đó sẽ giữ nguyên và không thay đổi, nếu nút đó bấm sai thời điểm, tất cả các nút đã nhấn sẽ bật lên, sau đó Ban phải nhấn nút lại từ đầu.

Hay lú lẫn nên Ban lỡ làm rớt mật khẩu khi đang đi về nhà. Thế là Ban phải mò từng mật khẩu một. Ban không biết là cần nhấn ít nhất bao nhiêu nút để chắc chắn rằng sẽ mở được ổ khóa??

NOTE

Vì đáp án có thể rất lớn nên lấy đáp án chia dư cho ~10^9+7~

Input

Dòng đầu tiên chứa 1 số nguyên n là số nút của két sắt ( <n< 10^5)</p>

Output

In ra số lượng lần bấm ít nhất để chắc chắn sẽ mở két sắt.

Sample Input


3
Sample Output


7

Giải thích test đề

Giả sử mật khẩu đúng là nhấn lần lượt các nút 1 2 3.

Đầu tiên Ban nhấn nút 2 thì sai nên bật lên lại(lần 1), Ban biết chắc chắn rằng số 2 nhấn đầu tiên là sai nên Ban bấm số 3, nút số 3 lại bật lên(lần 2)... "ơ, lại sai rồi, thế chắc chắn rằng nút đầu tiên luôn luôn là số 1", sau đó Ban nhấn nút số 1(lần 3) và không có gì xảy ra cả, Ban lại nhấn nút số 3(lần 4) thì cả nút số 1 và số 3 bật lên, Ban lại nghĩ :"vậy chắc chắn phải nhấn nút số 1 đầu tiên, sau đó phải nhấn nút số 2 và cuối cùng là nhấn nút số 3", sau đó Ban lại nhấn lần lượt nút số 1(lần 5) rồi số 2(lần 6) và số 3(lần 7) và chiếc két sắt đã mở ra. Vậy sau ít nhất 7 lần thì chiếc két sắt chắc chắn mở ra.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.