CF1142D.Foreigner

Traveling around the world you noticed that many shop owners raise prices to inadequate values if the see you are a foreigner.

You define inadequate numbers as follows:

• all integers from $1$ to $9$ are inadequate;
• for an integer $x \ge 10$ to be inadequate, it is required that the integer $\lfloor x / 10 \rfloor$ is inadequate, but that's not the only condition. Let's sort all the inadequate integers. Let $\lfloor x / 10 \rfloor$ have number $k$ in this order. Then, the integer $x$ is inadequate only if the last digit of $x$ is strictly less than the reminder of division of $k$ by $11$.

Here $\lfloor x / 10 \rfloor$ denotes $x/10$ rounded down.

Thus, if $x$ is the $m$-th in increasing order inadequate number, and $m$ gives the remainder $c$ when divided by $11$, then integers $10 \cdot x + 0, 10 \cdot x + 1 \ldots, 10 \cdot x + (c - 1)$ are inadequate, while integers $10 \cdot x + c, 10 \cdot x + (c + 1), \ldots, 10 \cdot x + 9$ are not inadequate.

The first several inadequate integers are $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32 \ldots$. After that, since $4$ is the fourth inadequate integer, $40, 41, 42, 43$ are inadequate, while $44, 45, 46, \ldots, 49$ are not inadequate; since $10$ is the $10$-th inadequate number, integers $100, 101, 102, \ldots, 109$ are all inadequate. And since $20$ is the $11$-th inadequate number, none of $200, 201, 202, \ldots, 209$ is inadequate.

You wrote down all the prices you have seen in a trip. Unfortunately, all integers got concatenated in one large digit string $s$ and you lost the bounds between the neighboring integers. You are now interested in the number of substrings of the resulting string that form an inadequate number. If a substring appears more than once at different positions, all its appearances are counted separately.

环游世界时，你注意到许多店主在发现你是外国人时，会将商品价格抬高至“不恰当的数值”。

你将“不恰当数”定义如下：

• 所有从 $1$ 到 $9$ 的整数均为不恰当数；
• 对于整数 $x \ge 10$，若其为不恰当数，则首先要求 $\lfloor x / 10 \rfloor$ 是不恰当数；但这并非唯一条件。我们将所有不恰当数按升序排列。设 $\lfloor x / 10 \rfloor$ 在该序列中排第 $k$ 位。那么，仅当 $x$ 的个位数字严格小于 $k$ 除以 $11$ 的余数时，$x$ 才是不恰当数。

其中 $\lfloor x / 10 \rfloor$ 表示 $x/10$ 向下取整。

因此，若 $x$ 是升序排列下的第 $m$ 个不恰当数，且 $m$ 除以 $11$ 的余数为 $c$，则整数 $10 \cdot x + 0,\, 10 \cdot x + 1,\, \ldots,\, 10 \cdot x + (c - 1)$ 均为不恰当数，而整数 $10 \cdot x + c,\, 10 \cdot x + (c + 1),\, \ldots,\, 10 \cdot x + 9$ 均不是不恰当数。

前若干个不恰当数为：$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, \ldots$。随后，由于 $4$ 是第 $4$ 个不恰当数，故 $40, 41, 42, 43$ 是不恰当数，而 $44, 45, 46, \ldots, 49$ 不是不恰当数；由于 $10$ 是第 $10$ 个不恰当数，故 $100, 101, 102, \ldots, 109$ 全部是不恰当数；又因 $20$ 是第 $11$ 个不恰当数，故 $200, 201, 202, \ldots, 209$ 全都不是不恰当数。

你在旅途中记录下了所见的所有价格。不幸的是，所有整数被拼接成一个巨大的数字字符串 $s$，你丢失了相邻整数之间的分隔边界。你现在关心的是：该字符串中，有多少个子串（substring）所表示的数字是不恰当数？若某个子串在不同位置多次出现，则每次出现均单独计数。

The only line contains the string $s$ ($1 \le |s| \le 10^5$), consisting only of digits. It is guaranteed that the first digit of $s$ is not zero.

仅有一行，包含字符串 $s$（$1 \le |s| \le 10^5$），该字符串仅由数字组成。保证 $s$ 的首位数字不为零。

In the only line print the number of substrings of $s$ that form an inadequate number.

在唯一的一行中输出字符串 $s$ 中构成不充分数的子串个数。

In the first example the inadequate numbers in the string are $1, 2, 4, 21, 40, 402$.

In the second example the inadequate numbers in the string are $1$ and $10$, and $1$ appears twice (on the first and on the second positions).

在第一个例子中，字符串中的不充分数字为 $1, 2, 4, 21, 40, 402$。

在第二个例子中，字符串中的不充分数字为 $1$ 和 $10$，且 $1$ 出现了两次（分别位于第一和第二位置）。