D. Foreignertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputTraveling 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.InputThe 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.OutputIn the only line print the number of substrings of s that form an inadequate number.ExamplesInput
4021
Output
6
Input
110
Output
3
NoteIn 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).
4021

6 
['dp', '*2800']