Giải bài trực tuyến

"Trung thu là tết thiếu nhi

Mà sao người lớn lại đi chơi nhiều

Chơi nhiều rồi lại làm liều

Làm liều lại có thêm nhiều thiếu nhi."

Vẫn biết trung thu là một dịp tốt để đi chơi với gấu và làm liều, nhưng trăng sáng như thế, Kid không được bay lượn trên bầu trời hay đi ăn trộm thì phí. Hiểu rõ 'tâm tư nguyện vọng' của Kid, một tuần trước trung thu, ông Jirokichi đã gửi thư thách Kid có thể lấy được cặp bánh trung thu bằng vàng nguyên chất của mình. Và tất nhiên, như mọi khi, Kid nhận lời và giờ cậu đang hí hoáy chiếc két để lấy được cặp bánh trung thu mà ông Jirokichi đã thách thức (ăn trộm như chỗ không người :v). Nhưng mọi việc không chỉ đơn giản như thế, chiếc két được mã hóa cực kì chắc chắn, chỉ cần sai mật khẩu nhập vào, quả bom trong chiếc két sẽ phát nổ và cặp bánh sẽ tiêu tan, hiển nhiên Kid sẽ là người thua cuộc. May mắn thay, trong khi cải trang thành người phục vụ ông Jirokichi , cậu đã 'mượn' được tờ giấy có chứa mật khẩu của chiếc két. Trên tờ giấy đó có chứa một bài toán, mà đáp số của nó chính là mật khẩu của chiếc két. Tất nhiên, do sợ sẽ làm rơi laptop khi đang bay trên trời, nên Kid đã không mang theo máy tính, vì thế việc giải bài toán trên trở nên vô cùng khó khăn. Hãy giúp đỡ Kid giải bài toán trên, rất có thể sau khi đã mở được chiếc két, Kid sẽ tặng bạn một chiếc bánh trung bằng vàng đó.

Bài toán trên tờ giấy của ông Jirokichi như sau:

Cho một xâu S , S chỉ chứa các số 0 đến 9. Tính tổng các DÃY CON LIÊN TIẾP của S mod 10^9+7

Input

• Một dòng duy nhất chứa xâu S

Output

• Một số duy nhất là kết quả của bài toán.

Giới hạn:

Với length(s) là độ dài của xâu S:

• 50% số test length(S) ≤ 100
• 50% số test còn lại length(s) ≤ 10^6

Example

Input:
737

Output:
864
864

Giải thích: 7 + 3 + 7 + 73 + 37 + 737 = 864