有时讨价还价并不容易达成协议。目前 Sasha 和 Vova 无法达成协议:Sasha 给出尽可能高的价格,然后 Vova 希望从价格中删除尽可能多的数字。更详细地说,Sasha 命名一些整数价格 $$$n$$$,Vova 从价格中删除(连续)数字的非空子串,剩余的数字缩小了差距,所得整数就是价格。
例如,如果Sasha的名字为$$$1213121$$$,Vova可以删除子字符串$$$1312$$$,结果为$$$121$$$。
结果允许包含前导零。如果 Vova 删除所有数字,则价格被视为 $$$0$$$。
Sasha 想要提出一些约束,以便 Vova 不能仅仅删除所有数字,但他需要一些支持这些约束的参数。首先,他想要计算 Vova 移动后所有可能产生的价格的总和。
帮助 Sasha 计算这个总和。由于答案可能非常大,因此打印它对 $$$10^9 + 7$$$ 取模。
输入
第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \le n < 10^{10^5}$$$)。
输出
在唯一的行中打印所需的总和模 $$$10^9 + 7$$$。
示例
输入 #1
107
输出 #1
42
输入 #2
100500100500
输出 #2
428101984
注意
考虑第一个例子。
Vova 可以选择删除 $$$1$$$、$$$0$$$、$$$7$$$、$$$10$$$、$$$07$$$ 或 $$$107$$$。结果是 $$$07$$$、$$$17$$$、$$$10$$$、$$$7$$$、$$$1$$$、$$$0$$$。他们的总和是$$$42$$$。