Igor the analyst is at work. He learned about a feature in his text editor called "Replace All". Igor is too bored at work and thus he came up with the following problem:

Given two strings x and y which consist of the English letters 'A' and 'B' only, a pair of strings (s, t) is called good if:

  * s and t consist of the characters '0' and '1' only.
  * 1 ≤ |s|, |t| ≤ n, where |z| denotes the length of string z, and n is a fixed positive integer.
  * If we replace all occurrences of 'A' in x and y with the string s, and replace all occurrences of 'B' in x and y with the string t, then the two obtained from x and y strings are equal. 



For example, if x = AAB, y = BB and n = 4, then (01, 0101) is one of good pairs of strings, because both obtained after replacing strings are "01010101".

The flexibility of a pair of strings x and y is the number of pairs of good strings (s, t). The pairs are ordered, for example the pairs (0, 1) and (1, 0) are different.

You're given two strings c and d. They consist of characters 'A', 'B' and '?' only. Find the sum of flexibilities of all possible pairs of strings (c', d') such that c' and d' can be obtained from c and d respectively by replacing the question marks with either 'A' or 'B', modulo 109 + 7.

Input

The first line contains the string c (1 ≤ |c| ≤ 3·105).

The second line contains the string d (1 ≤ |d| ≤ 3·105).

The last line contains a single integer n (1 ≤ n ≤ 3·105).

Output

Output a single integer: the answer to the problem, modulo 109 + 7.

Examples

Input

A?
?
3


Output

2


Input

A
B
10


Output

2046

Note

For the first sample, there are four possible pairs of (c', d').

If (c', d') = (AA, A), then the flexibility is 0.

If (c', d') = (AB, A), then the flexibility is 0.

If (c', d') = (AA, B), then the flexibility is 2, as the pairs of binary strings (1, 11), (0, 00) are the only good pairs.

If (c', d') = (AB, B), then the flexibility is 0.

Thus, the total flexibility is 2.

For the second sample, there are 21 + 22 + ... + 210 = 2046 possible binary strings of length not greater 10, and the set of pairs of good strings is precisely the set of pairs (s, s), where s is a binary string of length not greater than 10.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskG solver = new TaskG();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskG {
        static final long MODULO = (long) (1e9 + 7);

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            String c = in.next();
            String d = in.next();
            int n = in.nextInt();
            long res = 0;
            long waysEqual = 0;
            if (c.length() == d.length()) {
                waysEqual = 1;
                for (int i = 0; i < c.length(); ++i) {
                    char ac = c.charAt(i);
                    char ad = d.charAt(i);
                    if (ac == '?') {
                        if (ad == '?') {
                            waysEqual = waysEqual * 2 % MODULO;
                        }
                    } else if (ad == '?') {

                    } else {
                        if (ac != ad) {
                            waysEqual = 0;
                            break;
                        }
                    }
                }
                long total = 1;
                for (int i = 0; i < n; ++i) {
                    total = total * 2 % MODULO;
                }
                total = ((total * 2 - 2) % MODULO + MODULO) % MODULO;
                res = (res + total * total % MODULO * waysEqual) % MODULO;
            }

            long[] nonperiodic = new long[n + 1];
            nonperiodic[0] = 1;
            for (int i = 1; i <= n; ++i) nonperiodic[i] = 2 * nonperiodic[i - 1] % MODULO;
            long[] uptoValid = new long[n + 1];
            for (int i = 1; i <= n; ++i) {
                uptoValid[i] = uptoValid[i - 1] + nonperiodic[i];
                uptoValid[i] %= MODULO;
            }
            for (int i = 1; i <= n; ++i) {
                for (int j = 2 * i; j <= n; j += i) {
                    nonperiodic[j] -= nonperiodic[i];
                    if (nonperiodic[j] < 0) nonperiodic[j] += MODULO;
                }
            }

            long anyValid = 0;
            for (int i = 1; i <= n; ++i) {
                long maxTimes = n / i;
                anyValid = (anyValid + nonperiodic[i] * maxTimes % MODULO * maxTimes) % MODULO;
            }

            int na = 0;
            int nb = 0;
            int qPlus = 0;
            int qMinus = 0;
            for (int i = 0; i < c.length(); ++i) {
                char ac = c.charAt(i);
                if (ac == 'A') ++na;
                else if (ac == 'B') ++nb;
                else ++qPlus;
            }
            for (int i = 0; i < d.length(); ++i) {
                char ad = d.charAt(i);
                if (ad == 'A') --na;
                else if (ad == 'B') --nb;
                else ++qMinus;
            }
            na -= qMinus;
            qPlus += qMinus;
            qMinus = 0;
            long[] invs = new long[qPlus + 1];
            if (qPlus > 0)
                invs[1] = 1;
            for (int i = 2; i <= qPlus; ++i) {
                invs[i] = (MODULO - invs[((int) (MODULO % i))] * (MODULO / i) % MODULO) % MODULO;
                if (invs[i] * i % MODULO != 1) throw new RuntimeException();
            }
            long comb = 1;
            for (int nPlus = 0; nPlus <= qPlus; ++nPlus) {
                if (nPlus > 0) {
                    comb = comb * (qPlus - nPlus + 1) % MODULO * invs[nPlus] % MODULO;
                }
                int deltaMul = na + nPlus;
                int bMul = c.length() - d.length();
                if (deltaMul == 0 && bMul == 0) {
                    res = ((res + (comb - waysEqual) * anyValid) % MODULO + MODULO) % MODULO;
                } else {
                    int g = gcd(Math.abs(deltaMul), Math.abs(bMul));
                    deltaMul /= g;
                    bMul /= g;
                    if (deltaMul != 0) {
                        if (deltaMul < 0) {
                            deltaMul = -deltaMul;
                            bMul = -bMul;
                        }
                        int lb = deltaMul;
                        int la = lb - bMul;
                        if (la > 0) {
                            res = (res + comb * uptoValid[n / Math.max(la, lb)]) % MODULO;
                        }
                    }
                }
            }

            out.println(res);
        }

        private int gcd(int a, int b) {
            while (b > 0) {
                int t = a % b;
                a = b;
                b = t;
            }
            return a;
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

