У Казака Вуса есть две бинарные строки, то есть строки, которые состоят только из «0» и «1». Назовем эти строки $$$a$$$ и $$$b$$$. Известно, что $$$|b| \leq |a|$$$, то есть длина $$$b$$$ не более $$$a$$$.

Казак рассматривает каждую подстроку длины $$$|b|$$$ строки $$$a$$$. Назовем эту подстроку $$$c$$$. Он сопоставляет соответствующие символы в $$$b$$$ и $$$c$$$, после чего считает количество позиций, где эти две строки различны. Назовем эту функцию $$$f(b, c)$$$.

Например, пусть $$$b = 00110$$$, а $$$c = 11000$$$. В этих строках первая, вторая, третья и четвертая позиции различны.

Казак Вус считает количество таких подстрок $$$c$$$, что $$$f(b, c)$$$ — четное.

Например, пусть $$$a = 01100010$$$, а $$$b = 00110$$$. У $$$a$$$ есть четыре подстроки длины $$$|b|$$$: $$$01100$$$, $$$11000$$$, $$$10001$$$, $$$00010$$$.

• $$$f(00110, 01100) = 2$$$;
• $$$f(00110, 11000) = 4$$$;
• $$$f(00110, 10001) = 4$$$;
• $$$f(00110, 00010) = 1$$$.

Поскольку в трех подстроках $$$f(b, c)$$$ четное, то ответ — $$$3$$$.

Вус не умеет находить ответ для больших строк, поэтому просит вас помочь ему в этом.