许多菲律宾人沉迷于一款风靡全球的全新赛马动漫游戏，这并不令人惊讶。毕竟，“Philippines”（菲律宾）这个名字可以翻译为“马匹爱好者的土地”。

许多人在接触到新的粉丝圈时会变得非常令人讨厌。即使是完全不相关的事情，他们也会想方设法把话题引到马身上。最糟糕的是，你知道这个人几个月前根本不关心赛马，现在却装作专家！

例如，假设你正在为 ICPC Manila 2025 的题目进行头脑风暴，然后一个人突然说道：

“你知道吗？菲律宾 2012 年的三冠王 Hagdang Bato 是 Northern Dancer 的后代，而 Northern Dancer 是极具影响力的日本赛马 Northern Taste 的种马，人们普遍认为 Northern Taste 是——的灵感来源。”

即使在你让他们闭嘴并要求专注于工作之后，他们还是会说：

“好吧，Hagdang Bato 字面意思可以翻译为‘石阶’。所以，如果 $n$ 是一个不包含数字 $0$ 的正整数，我们可以定义 $H(n)$ 为将 $n$ 的数字按非递减顺序“排序”后得到的数字。就像楼梯一样！”

例如，$H(1971) = 1179$ 且 $H(3) = 3$。嗯，等等，这可能很有趣……

令 $s$ 为一个由非零数字组成的字符串。请计算 $s$ 的所有非空连续子串的 $H(\text{int}(s[i...j]))$ 之和。输出该和（模 1000696967）。

为了 Hagdang Bato，做吧。

令 $s$ 为 1-indexed（从 1 开始索引）。如果 $1 \le i \le j \le |s|$，则子串 $s[i...j]$ 对应于字符的连续片段 $s_i s_{i+1} \dots s_j$。字符串 $s$ 共有 $|s|(|s| + 1)/2$ 个非空子串。

此外，$\text{int}(\dots)$ 是一个函数，它接受一个字符串作为参数，并将其转换为整数（使用十进制）。

输入格式

输入包含一行，即字符串 $s$。

输出格式

输出一行，包含一个整数，即所需的和（模 1000696967）。

数据范围

$1 \le |s| \le 5 \times 10^5$ $s$ 仅由非零数字组成。

样例

输入 1

3141

输出 1

1432

输入 2

1

输出 2

1

输入 3

11234567891234567891

输出 3

43138332

说明

如果 $s = 3141$，它有 10 个非空子串：

• $s[1...1]$ 是 3，且 $H(3) = 3$。
• $s[2...2]$ 是 1，且 $H(1) = 1$。
• $s[3...3]$ 是 4，且 $H(4) = 4$。
• $s[4...4]$ 是 1，且 $H(1) = 1$。
• $s[1...2]$ 是 31，且 $H(31) = 13$。
• $s[2...3]$ 是 14，且 $H(14) = 14$。
• $s[3...4]$ 是 41，且 $H(41) = 14$。
• $s[1...3]$ 是 314，且 $H(314) = 134$。
• $s[2...4]$ 是 141，且 $H(141) = 114$。
• $s[1...4]$ 是 3141，且 $H(3141) = 1134$。

将它们相加：

$3 + 1 + 4 + 1 + 13 + 14 + 14 + 134 + 114 + 1134 = 1432$。