{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/PALIN3/mandarin/MINXOR.pdf\"\u003eMandarin Chinese\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/PALIN3/russian/MINXOR.pdf\"\u003eRussian\u003c/a\u003e as well.\u003c/h3\u003e\n\u003cp\u003e\nMike likes strings. He is also interested in algorithms. A few days ago he discovered for himself a very nice problem:\n\u003c/p\u003e\n\u003cp\u003e\u003ci\u003e\u003cbr /\u003e\nYou are given a digit string \u003cb\u003eS\u003c/b\u003e. You need to count the number of substrings of \u003cb\u003eS\u003c/b\u003e, which are palindromes.\u003cbr /\u003e\n\u003c/i\u003e\u003c/p\u003e\n\u003cp\u003e\nDo you know how to solve it? Good. Mike will make the problem a little bit more difficult for you.\n\u003c/p\u003e\n\u003cp\u003e\u003ci\u003e\u003cbr /\u003e\nYou are given a digit string \u003cb\u003eS\u003c/b\u003e. You need to count the number of substrings of \u003cb\u003eS\u003c/b\u003e, which are palindromes without leading zeros and can be divided by 3 without a remainder.\u003cbr /\u003e\n\u003c/i\u003e\u003c/p\u003e\n\u003cp\u003e\nA string is a palindrome if it reads the same backward as forward. A string is a palindrome without leading zeros if it reads the same backward as forward and doesn\u0027t start with symbol \u00270\u0027. A string is a digit string, if it doesn\u0027t contain any symbols except \u00270\u0027, \u00271\u0027, \u00272\u0027, ..., \u00279\u0027.\n\u003c/p\u003e\n\u003cp\u003e\nPlease, note that you should consider string \"0\" as a palindrome without leading zeros.\n\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cp\u003eThe first line of the input contains a digit string \u003cb\u003eS\u003c/b\u003e.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eYour output should contain the only integer, denoting the number of substrings of \u003cb\u003eS\u003c/b\u003e, which are palindromes without leading zeros and can be divided by 3 without a remainder.\u003c/p\u003e\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cp\u003e1 ≤ \u003cb\u003e|S|\u003c/b\u003e ≤ 1 000 000\u003c/p\u003e\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n1045003\n\n\u003cb\u003eOutput:\u003c/b\u003e\n4\n\u003c/pre\u003e\n\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003e\nIn the example you should count \u003cb\u003eS\u003c/b\u003e[2..2] \u003d \"0\", \u003cb\u003eS\u003c/b\u003e[5..5] \u003d \"0\", \u003cb\u003eS\u003c/b\u003e[6..6] \u003d \"0\" and \u003cb\u003eS\u003c/b\u003e[7..7] \u003d \"3\".\n\u003c/p\u003e\n"}}]}