12104번 - 순환 순열

문제

두 바이너리 문자열 A와 B가 주어졌을 때, A와 XOR 했을 때, 0이 나오는 B의 순환 순열의 개수를 구하는 프로그램을 작성하시오.

순환 순열이란 순열 P = P₀, P₁, ..., P_N-1이 있을 때, 왼쪽으로 k번 순환 이동시킨 순열이다. 즉, P를 k번 순환 이동 시키면, P_i -> P_{i+k mod n} 이 된다.

입력

첫째 줄에 A, 둘째 줄에 B가 주어진다. A와 B의 길이는 10⁵를 넘지 않는 자연수이며, 두 문자열의 길이는 같다.

출력

첫째 줄에 A와 XOR했을 때, 0이 나오는 B의 순환 순열의 개수를 출력한다.

제한

힌트