{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $P$\n$S$"},{"iden":"sample input 1","content":"4 3\n3543"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"4 2\n2020"},{"iden":"sample output 2","content":"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."},{"iden":"sample input 3","content":"20 11\n33883322005544116655"},{"iden":"sample output 3","content":"68"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}