Cho một số nguyên n (số lượng số 1), hãy tính tổng các số nguyên được tạo ra từ n số 1 mà không có số nào trùng nhau. Ví dụ có 3 số 111 tạo được 3 số 1, 11, 111.

Đầu vào:

Từ thiết bị chuẩn n (n ≤ ~10^{18}~)

Đầu ra:

Xuất ra thiết bị chuẩn là số nguyên đem chia module 10^9+7.

Ví dụ

Input

3

Output

123