{"problem":{"name":"Divisible Substring","description":{"content":"Takahashi has a string $S$ of length $N$ consisting of digits from `0` through `9`. He loves the prime number $P$. He wants to know how many non-empty (contiguous) substrings of $S$ - there are $N \\ti","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc158_e"},"statements":[{"statement_type":"Markdown","content":"Takahashi has a string $S$ of length $N$ consisting of digits from `0` through `9`.\nHe loves the prime number $P$. He wants to know how many non-empty (contiguous) substrings of $S$ - there are $N \\times (N + 1) / 2$ of them - are divisible by $P$ when regarded as integers written in base ten.\nHere substrings starting with a `0` also count, and substrings originated from different positions in $S$ are distinguished, even if they are equal as strings or integers.\nCompute this count to help Takahashi.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $S$ consists of digits.\n*   $|S| = N$\n*   $2 \\leq P \\leq 10000$\n*   $P$ is a prime number.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $P$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc158_e","tags":[],"sample_group":[["4 3\n3543","6\n\nHere $S$ = `3543`. There are ten non-empty (contiguous) substrings of $S$:\n\n*   `3`: divisible by $3$.\n    \n*   `35`: not divisible by $3$.\n    \n*   `354`: divisible by $3$.\n    \n*   `3543`: divisible by $3$.\n    \n*   `5`: not divisible by $3$.\n    \n*   `54`: divisible by $3$.\n    \n*   `543`: divisible by $3$.\n    \n*   `4`: not divisible by $3$.\n    \n*   `43`: not divisible by $3$.\n    \n*   `3`: divisible by $3$.\n    \n\nSix of these are divisible by $3$, so print $6$."],["4 2\n2020","10\n\nHere $S$ = `2020`. There are ten non-empty (contiguous) substrings of $S$, all of which are divisible by $2$, so print $10$.\nNote that substrings beginning with a `0` also count."],["20 11\n33883322005544116655","68"]],"created_at":"2026-03-03 11:01:14"}}