{"problem":{"name":"Three Days Ago","description":{"content":"The string `20230322` can be rearranged into `02320232`, which is a repetition of `0232` twice.   Similarly, a string consisting of digits is said to be **happy** when it can be rearranged into (or al","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc295_d"},"statements":[{"statement_type":"Markdown","content":"The string `20230322` can be rearranged into `02320232`, which is a repetition of `0232` twice.  \nSimilarly, a string consisting of digits is said to be **happy** when it can be rearranged into (or already is) a repetition of some string twice.  \nYou are given a string $S$ consisting of digits. Find the number of pairs of integers $(l,r)$ satisfying all of the following conditions.\n\n*   $1 \\le l \\le r \\le |S|$. ($|S|$ is the length of $S$.)\n*   The (contiguous) substring formed of the $l$\\-th through $r$\\-th characters of $S$ is happy.\n\n## Constraints\n\n*   $S$ is a string consisting of digits whose length is between $1$ and $5 \\times 10^5$, inclusive.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc295_d","tags":[],"sample_group":[["20230322","4\n\nWe have $S=$ `20230322`.\nHere are the four pairs of integers $(l,r)$ that satisfy the condition: $(1,6)$, $(1,8)$, $(2,7)$, and $(7,8)$."],["0112223333444445555556666666777777778888888889999999999","185\n\n$S$ may begin with `0`."],["3141592653589793238462643383279502884197169399375105820974944","9"]],"created_at":"2026-03-03 11:01:14"}}