const int maxn = 3e5 + ;

 const int maxnode =  *  + ;

 const int mod = ;

 int ch[maxnode][];

 struct Trie {

     int sz;

     bool IsWord[maxnode];

     Trie() {

         sz = ;

         init(ch[], );

     }

     void insert(char *t) {

         int len = strlen(t), u = ;

         for (int i = ; i < len; ++i) {

             if (!ch[u][t[i] - 'a']) {

                 init(ch[sz], );

                 IsWord[sz] = false;

                 ch[u][t[i] - 'a'] = sz++;

             }

             u = ch[u][t[i] - 'a'];

         }

         IsWord[u] = true;

     }

     int find(int pos, char *str, int *dp) {

         int ret = , u = ;

         for (int i = pos; str[i]; ++i) {

             if (!ch[u][str[i] - 'a'])    return ret;

             u = ch[u][str[i] - 'a'];

             if (IsWord[u])    ret = ((ll)ret + dp[i + ]) % mod;

         }

         return ret;

     }

 };

 char str[maxn], t[];

 int S, L, dp[maxn], kase;

 int main() {

     while (~scanf("%s", str)) {

         Trie T;

         for (scanf("%d", &S); S; S--) {

             scanf("%s", t);

             T.insert(t);

         }

         L = strlen(str);

         dp[L] = ;

         for (int i = L - ; ~i; --i) {

             dp[i] = T.find(i, str, dp);

         }

         printf("Case %d: %d\n", ++kase, dp[]);

     }

     return ;

 }