{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003eViktoria is so easily offended. She was also offended by Alex during their walk. It is known that Alex and Viktoria were walking \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e minutes. And every minute Viktoria was either offended or not offended by Alex. Since we are all programmers, let\u0027s denote these \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e minutes of Viktoria\u0027s state as a string of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e bits. So, the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th bit of the string is \u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e if she was offended in the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th minute, otherwise this bit is \u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eAlex considers that Viktoria takes offense at him too often. And he likes to prove everything. That\u0027s why Alex wants to count the number of time periods where her offence was \u003cspan class\u003d\"tex-font-style-bf\"\u003estrictly greater\u003c/span\u003e than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e. A pair of numbers \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e)\u003c/span\u003e, where \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, is considered to be a time period. Viktoria\u0027s offense during some period is a ratio of the amount of minutes she took offense to the total amount of minutes in a period. More formally, Viktoria\u0027s offense during the period \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e)\u003c/span\u003e is \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"https://codeforces.com/predownloaded/9a/5c/9a5cbcad63e534293af9230a8f82b29145374c3b.png\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ecnt\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e is an amount of ones in the segment \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e)\u003c/span\u003e of the bit string, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ecnt\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eall\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the total amount of characters in the bit string from the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003c/span\u003e-th position to the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/span\u003e-th position.\u003c/p\u003e\n\u003cp\u003eHelp Alex to prove to Viktoria that she takes offense too often!\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains the description of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e in the form of two space-separated integers: \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eP\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e. (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003eP\u003c/i\u003e ≤ 1000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eQ\u003c/i\u003e ≤ 1000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eP\u003c/i\u003e ≤ \u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e), i. e. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e is equal to \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"https://codeforces.com/predownloaded/43/5f/435f12e5c626a9be5583dd7bd0a4451aae5611d3.png\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. \u003c/p\u003e\n\u003cp\u003eThe next line contains a string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e. It consists of the characters \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e\u0027 and \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e\u0027. The length of the string is positive and doesn\u0027t exceed \u003cspan class\u003d\"tex-span\"\u003e200 000\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput the number of segments \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e)\u003c/span\u003e, where Viktoria\u0027s offense is strictly greater than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3 10\u003cbr\u003e10110\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e13\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e9 10\u003cbr\u003e010100101101\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e7\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}