{"trustable":true,"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePiva has recently bought a wonderful beach house at \u003cspan class\u003d\"tex-font-style-it\"\u003ePraia do Forte\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eAfter deciding that his house would be as colorful as a rainbow, Piva painted his living room in tiles of different colors. More specifically, Piva\u0027s living room can be seen as a row of $$$n$$$ tiles such that the $$$i$$$-th of them has color $$$s_i$$$, where $$$s$$$ is a string composed of lowercase English characters.\u003c/p\u003e\u003cp\u003ePiva now wants to put his brand-new \u003cspan class\u003d\"tex-font-style-it\"\u003ecolor changing\u003c/span\u003e sofa in his room. The sofa is $$$m$$$ ($$$m \\leq n$$$) tiles long and should be put in the room in a way that it fits entirely on $$$m$$$ consecutive tiles. Moreover, Piva wants the colors of the sofa and of the floor to match. We say that their colors match if the color of a sofa tile matches with the color of the floor tile \u003cspan class\u003d\"tex-font-style-bf\"\u003eright below\u003c/span\u003e it. To accomplish that, Piva may change the colors of the sofa according to its specification.\u003c/p\u003e\u003cp\u003eThe sofa can be described by a string $$$t$$$ of zeroes and ones of length $$$m$$$, where each character in the string represents a tile of the sofa. Piva can pick the zero-tiles and change them all to the same color. The same can be done for one-tiles. Therefore, notice that it is impossible for two zero-tiles (same for one-tiles) to have different colors. Also, that means that the tiles of the sofa will have \u003cspan class\u003d\"tex-font-style-bf\"\u003eat most\u003c/span\u003e two different colors. For instance, suppose the string is \u003cspan class\u003d\"tex-font-style-tt\"\u003e101\u003c/span\u003e. That means we can color the sofa \u003cspan class\u003d\"tex-font-style-tt\"\u003eaba\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-tt\"\u003eaaa\u003c/span\u003e, but not \u003cspan class\u003d\"tex-font-style-tt\"\u003eabc\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eGiven the descriptions of Piva\u0027s living room and of his sofa, determine on how many positions his sofa can be placed. Notice that for each possible placement, the sofa colors can be chosen independently. Also, notice that the sofa can be put in any direction (left to right \u003cspan class\u003d\"tex-font-style-bf\"\u003eor\u003c/span\u003e right to left), but a position where it can be put in both directions should be counted only once.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains the string $$$s$$$ ($$$|s| \u003d n \\leq 2000$$$) – the living room description.\u003c/p\u003e\u003cp\u003eThe second line contains the string of zeroes and ones $$$t$$$ ($$$|t| \u003d m \\leq n$$$) – the sofa description.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer – the number of positions the sofa can be placed.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eaba\n10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eaba\n111\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eaaa\n101\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eabada\n101\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eaab\n100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example, we can put the sofa in two positions. \u003c/p\u003e\u003col\u003e \u003cli\u003e Position $$$[1, 2]$$$, color mapping $$$(0 \\rightarrow a, 1 \\rightarrow b)$$$, left to right. \u003c/li\u003e\u003cli\u003e Position $$$[2, 3]$$$, color mapping $$$(0 \\rightarrow b, 1 \\rightarrow a)$$$, left to right. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eNotice there are other correct direction and color mapping configurations for each of these positions. The ones shown above are just examples.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eIn the second example, there is no way to place the sofa and to choose its colors such that there is a color match.\u003c/p\u003e\u003cp\u003eIn the third example, we can put the sofa in $$$[1, 3]$$$, color mapping $$$(0 \\rightarrow a, 1 \\rightarrow a)$$$, left to right.\u003c/p\u003e\u003cp\u003eIn the fourth example, we can put the sofa in two positions:\u003c/p\u003e\u003col\u003e \u003cli\u003e Position $$$[1, 3]$$$, color mapping $$$(0 \\rightarrow a, 1 \\rightarrow b)$$$, left to right. \u003c/li\u003e\u003cli\u003e Position $$$[3, 5]$$$, color mapping $$$(0 \\rightarrow a, 1 \\rightarrow d)$$$, left to right. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eIn the fifth example, we can put the sofa in $$$[1, 3]$$$, color mapping $$$(0 \\rightarrow a, 1 \\rightarrow b)$$$, \u003cspan class\u003d\"tex-font-style-bf\"\u003eright to left\u003c/span\u003e.\u003c/p\u003e"}}]}