using System;
using System.Collections.Generic;

public class Test
{
    const long MOD = 1000000007;

    abstract class RegNode { }
    class SymbolNode : RegNode
    {
        public char Symbol;
        public SymbolNode(char c) => Symbol = c;
    }
    class ConcatNode : RegNode
    {
        public RegNode Left, Right;
        public ConcatNode(RegNode l, RegNode r) { Left = l; Right = r; }
    }
    class UnionNode : RegNode
    {
        public RegNode Left, Right;
        public UnionNode(RegNode l, RegNode r) { Left = l; Right = r; }
    }
    class StarNode : RegNode
    {
        public RegNode Inner;
        public StarNode(RegNode node) => Inner = node;
    }

    class RegexParser
    {
        string s;
        int pos;

        public RegNode Parse(string input)
        {
            s = input;
            pos = 0;
            return ParseExpression();
        }

        RegNode ParseExpression()
        {
            SkipWhite();
            if (pos >= s.Length) throw new Exception("Błąd w wyrażeniu");

            if (s[pos] == 'a' || s[pos] == 'b')
            {
                var node = new SymbolNode(s[pos]);
                pos++;
                SkipWhite();
                return node;
            }

            if (s[pos] == '(')
            {
                pos++;
                SkipWhite();
                var left = ParseExpression();
                SkipWhite();

                if (pos >= s.Length) throw new Exception("Brak zamknięcia nawiasu");

                if (s[pos] == '*')
                {
                    pos++;
                    SkipWhite();
                    if (pos >= s.Length || s[pos] != ')')
                        throw new Exception("Brak ) po *");
                    pos++;
                    SkipWhite();
                    return new StarNode(left);
                }
                if (s[pos] == '|')
                {
                    pos++;
                    SkipWhite();
                    var right = ParseExpression();
                    SkipWhite();
                    if (pos >= s.Length || s[pos] != ')')
                        throw new Exception("Brak ) w alternatywie");
                    pos++;
                    SkipWhite();
                    return new UnionNode(left, right);
                }
                // (R1R2)
                var rightConcat = ParseExpression();
                SkipWhite();
                if (pos >= s.Length || s[pos] != ')')
                    throw new Exception("Brak ) w konkatenacji");
                pos++;
                SkipWhite();
                return new ConcatNode(left, rightConcat);
            }
            throw new Exception("Niepoprawny symbol w wyrażeniu");
        }

        void SkipWhite()
        {
            while (pos < s.Length && char.IsWhiteSpace(s[pos]))
                pos++;
        }
    }

    class NFA
    {
        public List<(char symbol, int to)>[] transitions;
        public List<int>[] epsilons;
        public int Start;
        public int End;
        public int StateCount;

        public NFA(int capacity)
        {
            transitions = new List<(char symbol, int to)>[capacity];
            epsilons = new List<int>[capacity];
            for (int i = 0; i < capacity; i++)
            {
                transitions[i] = new List<(char symbol, int to)>();
                epsilons[i] = new List<int>();
            }
        }
    }

    class NfaBuilder
    {
        int idx = 0;
        public NFA Build(RegNode root)
        {
            int cap = CountNodes(root)*2 + 2;
            var nfa = new NFA(cap);
            var (s, e) = BuildRec(root, nfa);
            nfa.Start = s;
            nfa.End = e;
            nfa.StateCount = idx;
            return nfa;
        }
        (int start, int end) BuildRec(RegNode node, NFA nfa)
        {
            if (node is SymbolNode sym)
            {
                int s = idx++;
                int e = idx++;
                nfa.transitions[s].Add((sym.Symbol, e));
                return (s, e);
            }
            if (node is ConcatNode c)
            {
                var left = BuildRec(c.Left, nfa);
                var right = BuildRec(c.Right, nfa);
                nfa.epsilons[left.end].Add(right.start);
                return (left.start, right.end);
            }
            if (node is UnionNode u)
            {
                int s = idx++;
                int e = idx++;
                var left = BuildRec(u.Left, nfa);
                var right = BuildRec(u.Right, nfa);
                nfa.epsilons[s].Add(left.start);
                nfa.epsilons[s].Add(right.start);
                nfa.epsilons[left.end].Add(e);
                nfa.epsilons[right.end].Add(e);
                return (s, e);
            }
            if (node is StarNode st)
            {
                int s = idx++;
                int e = idx++;
                var inner = BuildRec(st.Inner, nfa);
                nfa.epsilons[s].Add(inner.start);
                nfa.epsilons[s].Add(e);
                nfa.epsilons[inner.end].Add(e);
                nfa.epsilons[inner.end].Add(inner.start);
                return (s, e);
            }
            throw new Exception("Nieznany typ węzła");
        }
        int CountNodes(RegNode node)
        {
            if (node is SymbolNode) return 1;
            if (node is ConcatNode c) return 1 + CountNodes(c.Left) + CountNodes(c.Right);
            if (node is UnionNode u) return 1 + CountNodes(u.Left) + CountNodes(u.Right);
            if (node is StarNode s)  return 1 + CountNodes(s.Inner);
            return 0;
        }
    }

    static List<int>[] EClosureAll(NFA nfa)
    {
        var closures = new List<int>[nfa.StateCount];
        for (int i = 0; i < nfa.StateCount; i++)
            closures[i] = EClosure(i, nfa);
        return closures;
    }
    static List<int> EClosure(int start, NFA nfa)
    {
        var stack = new Stack<int>();
        var visited = new bool[nfa.StateCount];
        var list = new List<int>();
        stack.Push(start);
        visited[start] = true;
        while (stack.Count > 0)
        {
            int s = stack.Pop();
            list.Add(s);
            foreach (int nxt in nfa.epsilons[s])
            {
                if (!visited[nxt])
                {
                    visited[nxt] = true;
                    stack.Push(nxt);
                }
            }
        }
        return list;
    }

    static long[] BuildTransitionMatrix(NFA nfa)
    {
        int N = nfa.StateCount;
        var closures = EClosureAll(nfa);
        long[] M = new long[N*N];
        for (int i = 0; i < N; i++)
        {
            foreach (int c in closures[i])
            {
                foreach (var (symbol, to) in nfa.transitions[c])
                {
                    foreach (int t in closures[to])
                    {
                        M[i*N + t] = (M[i*N + t] + 1) % MOD;
                    }
                }
            }
        }
        return M;
    }

    static void MatrixMul(long[] A, long[] B, long[] C, int N)
    {
        Array.Clear(C, 0, N*N);
        for (int i = 0; i < N; i++)
        {
            int iN = i*N;
            for (int k = 0; k < N; k++)
            {
                long val = A[iN + k];
                if (val == 0) continue;
                int kN = k*N;
                for (int j = 0; j < N; j++)
                {
                    long sum = C[iN + j] + val * B[kN + j];
                    if (sum >= 8000000000000000000L) sum %= MOD;
                    C[iN + j] = sum;
                }
            }
            // mod po każdej linii
            for (int j = 0; j < N; j++)
                C[iN + j] %= MOD;
        }
    }

    static long[] MatrixPow(long[] M, long exp, int N)
    {
        long[] res = new long[N*N];
        for (int i = 0; i < N; i++) 
            res[i*N + i] = 1;

        long[] baseMat = new long[N*N];
        Array.Copy(M, baseMat, N*N);

        long[] tmp = new long[N*N];

        while (exp > 0)
        {
            if ((exp & 1) == 1)
            {
                MatrixMul(res, baseMat, tmp, N);
                // swap
                var swp = res; 
                res = tmp; 
                tmp = swp;
            }
            MatrixMul(baseMat, baseMat, tmp, N);
            {
                var swp = baseMat;
                baseMat = tmp;
                tmp = swp;
            }
            exp >>= 1;
        }
        return res;
    }

    static long CountStrings(RegNode root, long L)
    {
        var nfaBuilder = new NfaBuilder();
        var nfa = nfaBuilder.Build(root);
        int N = nfa.StateCount;
        long[] M = BuildTransitionMatrix(nfa);

        var Mpow = MatrixPow(M, L, N);
        long result = Mpow[nfa.Start*N + nfa.End] % MOD;

        if (L == 0)
        {
            var startClosure = EClosure(nfa.Start, nfa);
            if (startClosure.Contains(nfa.End))
                result = (result + 1) % MOD;
        }
        return result;
    }

    public static void Main()
    {
        // Staram się wczytywać T bezpiecznie
        string tLine = Console.ReadLine();
        if (string.IsNullOrWhiteSpace(tLine))
        {
            // brak danych: np. brak testów
            return; // albo throw
        }

        int T = int.Parse(tLine.Trim());
        var parser = new RegexParser();

        for (int _t = 0; _t < T; _t++)
        {
            string line = Console.ReadLine();
            // zabezpieczenie przed nullem / pustym wierszem
            if (string.IsNullOrWhiteSpace(line))
            {
                // Możemy przerwać albo wczytać jeszcze raz itp.
                // Dla pewności mogę przerwać pętlę testów
                // break;
                // lub rzucić nowy wyjątek:
                throw new Exception("Błąd: pusty wiersz testu!");
            }

            line = line.Trim();
            int lastSpace = line.LastIndexOf(' ');
            if (lastSpace == -1)
            {
                throw new Exception("Brak spacji rozdzielającej wyrażenie i L w wierszu: " + line);
            }

            string reg = line.Substring(0, lastSpace).Trim();
            string lStr = line.Substring(lastSpace + 1).Trim();
            if (!long.TryParse(lStr, out long L))
            {
                throw new Exception("Nieprawidłowa liczba L: " + lStr);
            }

            // Parsuję wyrażenie
            var root = parser.Parse(reg);

            // Liczę
            long ans = CountStrings(root, L);
            Console.WriteLine(ans % MOD);
        }
    }
}