D. Foreigner
dp
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.
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.
In the only line print the number of substrings of \(s\) that form an inadequate number.
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).