Replace All

분석가 Igor는 일하는 중이다. 그는 자신의 텍스트 편집기에 있는 "Replace All"이라는 기능을 알게 되었다. Igor는 직장에서 너무 지루한 나머지 다음 문제를 생각해 냈다.

영문자 'A'와 'B'로만 이루어진 두 문자열 x와 y가 주어질 때, 문자열 쌍 (s, t)이 좋다는 것은 다음 조건을 만족한다는 뜻이다.

• s와 t는 문자 '0'과 '1'로만 이루어진다.
• 1 ≤ |s|, |t| ≤ n이다. 여기서 |z|는 문자열 z의 길이를 나타내며, n은 고정된 양의 정수이다.
• x와 y에 등장하는 모든 'A'를 문자열 s로 바꾸고, x와 y에 등장하는 모든 'B'를 문자열 t로 바꾸면, x와 y에서 각각 얻은 두 문자열이 같다.

예를 들어 x = AAB, y = BB, n = 4라면, (01, 0101)은 좋은 문자열 쌍 중 하나이다. 치환한 뒤 얻는 두 문자열이 모두 "01010101"이기 때문이다.

문자열 쌍 x와 y의 유연성은 좋은 문자열 쌍 (s, t)의 개수이다. 쌍에는 순서가 있으므로, 예를 들어 (0, 1)과 (1, 0)은 서로 다르다.

두 문자열 c와 d가 주어진다. 이 문자열들은 문자 'A', 'B', '?'로만 이루어진다. c와 d의 물음표를 각각 'A' 또는 'B'로 바꾸어 c'과 d'을 얻을 수 있는 모든 문자열 쌍 (c', d')의 유연성의 합을 109 + 7로 나눈 나머지를 구한다.

첫 번째 줄에 문자열 c (1 ≤ |c| ≤ 3·105)가 주어진다.

두 번째 줄에 문자열 d (1 ≤ |d| ≤ 3·105)가 주어진다.

마지막 줄에 하나의 정수 n (1 ≤ n ≤ 3·105)이 주어진다.

문제의 답을 109 + 7로 나눈 나머지를 하나의 정수로 출력한다.

첫 번째 예제에서 가능한 (c', d') 쌍은 네 가지이다.

(c', d') = (AA, A)이면 유연성은 0이다.

(c', d') = (AB, A)이면 유연성은 0이다.

(c', d') = (AA, B)이면 유연성은 2이다. 이때 이진 문자열 쌍 (1, 11), (0, 00)만이 좋은 쌍이기 때문이다.

(c', d') = (AB, B)이면 유연성은 0이다.

따라서 유연성의 총합은 2이다.

두 번째 예제에서 길이가 10 이하인 가능한 이진 문자열은 21 + 22 + ... + 210 = 2046개이며, 좋은 문자열 쌍의 집합은 정확히 (s, s) 꼴의 쌍들의 집합이다. 여기서 s은 길이가 10 이하인 이진 문자열이다.