HackerRank Count Strings Problem Solution

In this post, we will solve HackerRank Count Strings Problem Solution.

A regular expression is used to describe a set of strings. For this problem the alphabet is limited to ‘a’ and ‘b’.
We define R to be a valid regular expression if:
1) R is “a” or “b”.
2) R is of the form “(R1 R2)”, where R1 and R2 are regular expressions.
3) R is of the form “(R1 R2)” where R1 and R2 are regular expressions.
4) R is of the form “(R1)” where R1 is a regular expression. Regular expressions can be nested and will always have have two elements in the parentheses. (‘‘ is an element, ‘|’ is not; basically, there will always be pairwise evaluation) Additionally, *** will always be the second element; ‘(*a)’ is invalid.
The set of strings recognized by R are as follows:
1) If R is “a”, then the set of strings recognized = a.
2) If R is “b”, then the set of strings recognized = b.
3) If R is of the form “(R1 R2)” then the set of strings recognized = all strings which can be obtained by a concatenation of strings $1 and 82, where 81 is recognized by R₁ and $2 by
R2.
4) If R is of the form “(R1 R2)” then the set of strings recognized = union of the set of strings recognized by R1 and R2.

5) If R is of the form “(R1*)” then the the strings recognized are the empty string and the concatenation of an arbitrary number of copies of any string recognized by R1.
Task
Given a regular expression and an integer, L, count how many strings of length L are recognized by it.
Input Format
The first line contains the number of test cases T. T test cases follow. Each test case contains a regular expression, R, and an integer, L.

Output Format
Print T lines, one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 10 power 9 +7.

Sample Input

3  
((ab)|(ba)) 2  
((a|b)*) 5  
((a*)(b(a*))) 100

Sample Output

2  
32  
100

Explanation
For the first case, the only strings recognized are “ab” and “ba”. Of the 4 possible strings of length 2,2 of them fit that expression.
For the second case, the RegEx recognizes any string of any length containing only a’s and b ‘s. The number of strings of length 5 recognized by this expression is 25 = 32. For the third case, the RegEx recognizes any string having one b, preceeded and followed by any number of a’s. There are 100 strings of length 100 which have a single bin them.

HackerRank Count Strings Problem Solution

Count Strings C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
typedef struct _node{
  struct _node *next;
  int x;
  int y;
  struct _node *stack_pointer;
}node;
typedef struct _set{
  int size;
  int *list;
  int d;
  int index;
}set;
typedef struct _tree_node{

  enum {red,black} colour;

  set *data;

  struct _tree_node *left,*right,*parent;

}tree_node;
void sort_a(int *a,int size,int *new_size);
void merge(int *a,int *left,int *right,int left_size, int right_size,int *new_size);
void sort_a2(int *a,int *b,int *c,int size);
void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,int *c,int *left_c,int *right_c,int left_size, int right_size);
void addPlus(char *str);
int read_x(node *head);
node *read_stack_pointer(node *head);
void push(node **head,node *elem);
node *pop(node **head);
void hit_ab(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d,int flag);
void hit_plus(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void hit_pip(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void hit_left(node *b_stack,node **c_stack);
void hit_right(node **a_stack,node **b_stack,node **c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void process_star(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void process_plus(node **a_stack,int *size,int *u,int *v,int *o);
void process_pip(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
int find(int *list,int size,int x);
set *move(int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *old_set,int flag);
int compare_set(set *set1,set *set2);
void run(set **set_list,int *n_node_counter,int *n_size,int *n_u,int *n_v,int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *run_set,tree_node **root,int *prev);
int search(tree_node *root,set *x);
void left_rotate(tree_node **root,tree_node *x);
void right_rotate(tree_node **root,tree_node *y);
void reconstruct(tree_node **root,tree_node *x);
int normal_insert(tree_node **root,tree_node *x);
void insert(tree_node **root,tree_node *x);
void clean_tree(tree_node *root);
void clean_set(set **set_list,int n_node_counter);
void one(long long *a,int SIZE,int SIZE2);
void mul(long long *a,long long *b,int SIZE,int SIZE2);
void pown(long long *a,int n,long long *res,int SIZE,int SIZE2);

int main(){
  int T,L,i,j,node_counter,*u,*v,*o,*d,size,n_node_counter,*n_u,*n_v,n_size,*index,first_node;
  char str[300];
  node *a_stack,*b_stack,*c_stack,*last_node;
  set **set_list,*first_set;;
  tree_node *root;
  long long temp[400][400],ans[400][400],f;
  u=(int*)malloc(1000*sizeof(int));
  v=(int*)malloc(1000*sizeof(int));
  o=(int*)malloc(1000*sizeof(int));
  d=(int*)malloc(2000*sizeof(int));
  n_u=(int*)malloc(1000*sizeof(int));
  n_v=(int*)malloc(1000*sizeof(int));
  index=(int*)malloc(2000*sizeof(int));
  set_list=(set**)malloc(400000*sizeof(set*));
  scanf("%d",&T);
  while(T--){
    scanf("%s%d",str,&L);
    addPlus(str);
    a_stack=b_stack=c_stack=NULL;
    root=NULL;
    node_counter=size=n_node_counter=n_size=0;
    for(i=0;str[i]!='\0';i++)
      switch(str[i]){
        case 'a': hit_ab(&a_stack,&node_counter,&size,u,v,o,d,0); break;
        case 'b': hit_ab(&a_stack,&node_counter,&size,u,v,o,d,1); break;
        case '*': process_star(&a_stack,&node_counter,&size,u,v,o,d); break;
        case '+': hit_plus(&a_stack,&b_stack,c_stack,&node_counter,&size,u,v,o,d); break;
        case '|': hit_pip(&a_stack,&b_stack,c_stack,&node_counter,&size,u,v,o,d); break;
        case '(': hit_left(b_stack,&c_stack); break;
        case ')': hit_right(&a_stack,&b_stack,&c_stack,&node_counter,&size,u,v,o,d); break;
        default: break;
      }
    while(b_stack){
      i=read_x(b_stack);
      if(!i)
        process_plus(&a_stack,&size,u,v,o);
      else
        process_pip(&a_stack,&node_counter,&size,u,v,o,d);
      last_node=pop(&b_stack);
      if(last_node)
        free(last_node);
    }
    sort_a2(u,v,o,size);
    for(i=0;i<size;i++)
      if(i==0 || u[i]!=u[i-1])
        index[u[i]]=i;
    first_node=read_x(a_stack);
    last_node=pop(&a_stack);
    if(last_node)
      free(last_node);
    first_set=(set*)malloc(sizeof(set));
    first_set->list=(int*)malloc(sizeof(int));
    first_set->size=1;
    first_set->list[0]=first_node;
    run(set_list,&n_node_counter,&n_size,n_u,n_v,node_counter,size,u,v,o,d,index,first_set,&root,NULL);
    clean_tree(root);
    for(i=0;i<n_node_counter;i++)
      for(j=0;j<n_node_counter;j++)
        temp[i][j]=0;
    for(i=0;i<n_size;i++)
      temp[n_u[i]][n_v[i]]++;
    pown(&temp[0][0],L,&ans[0][0],n_node_counter,400);
    for(i=0,f=0;i<n_node_counter;i++)
      if(set_list[i]->d)
        f=(f+ans[0][set_list[i]->index])%MOD;
    printf("%lld\n",f);
    clean_set(set_list,n_node_counter);
  }
  return 0;
}
void sort_a(int *a,int size,int *new_size){

  if (size < 2){

    (*new_size)=size;

    return;

  }

  int m = (size+1)/2,i;

  int left[m],right[size-m];

  for(i=0;i<m;i++)

    left[i]=a[i];

  for(i=0;i<size-m;i++)

    right[i]=a[i+m];

  int new_l_size=0,new_r_size=0;

  sort_a(left,m,&new_l_size);

  sort_a(right,size-m,&new_r_size);

  merge(a,left,right,new_l_size,new_r_size,new_size);

  return;

}

void merge(int *a,int *left,int *right,int left_size, int right_size,int *new_size){

  int i = 0, j = 0,index=0;

  while (i < left_size|| j < right_size) {

    if (i == left_size) {

      a[index++] = right[j];

      j++;

    } else if (j == right_size) {

      a[index++] = left[i];

      i++;

    } else if (left[i] <= right[j]) {

      a[index++] = left[i];

      i++;

    } else {

      a[index++] = right[j];

      j++;

    }

    if(index>1&&a[index-2]==a[index-1])

      index--;

  }

  (*new_size)=index;

  return;

}
void sort_a2(int *a,int *b,int *c,int size){

  if (size < 2)

    return;

  int m = (size+1)/2,i;

  int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;

  left_a=(int*)malloc(m*sizeof(int));

  right_a=(int*)malloc((size-m)*sizeof(int));

  left_b=(int*)malloc(m*sizeof(int));

  right_b=(int*)malloc((size-m)*sizeof(int));
  left_c=(int*)malloc(m*sizeof(int));

  right_c=(int*)malloc((size-m)*sizeof(int));

  for(i=0;i<m;i++){

    left_a[i]=a[i];

    left_b[i]=b[i];
    left_c[i]=c[i];

  }

  for(i=0;i<size-m;i++){

    right_a[i]=a[i+m];

    right_b[i]=b[i+m];

    right_c[i]=c[i+m];

  }

  sort_a2(left_a,left_b,left_c,m);

  sort_a2(right_a,right_b,right_c,size-m);

  merge2(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);

  free(left_a);

  free(right_a);

  free(left_b);

  free(right_b);
  free(left_c);

  free(right_c);

  return;

}

void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,int *c,int *left_c,int *right_c,int left_size, int right_size){

  int i = 0, j = 0;

  while (i < left_size || j < right_size) {

    if (i == left_size) {

      a[i+j] = right_a[j];

      b[i+j] = right_b[j];
      c[i+j] = right_c[j];

      j++;

    } else if (j == right_size) {

      a[i+j] = left_a[i];

      b[i+j] = left_b[i];
      c[i+j] = left_c[i];

      i++;

    } else if (left_a[i] <= right_a[j]) {

      a[i+j] = left_a[i];

      b[i+j] = left_b[i];
      c[i+j] = left_c[i];

      i++;

    } else {

      a[i+j] = right_a[j];

      b[i+j] = right_b[j];
      c[i+j] = right_c[j];

      j++;

    }

  }

  return;

}
void addPlus(char *str){
  int i,j,len;
  len=strlen(str);
  for(i=0;i<len-1;i++)
    if(str[i]!='(' && str[i]!='|' && str[i+1]!='|' && str[i+1]!='*' && str[i+1]!=')'){
      for(j=len+1;j>i+1;j--)
        str[j]=str[j-1];
      str[i+1]='+';
      len++;
      i++;
    }
  return;
}
int read_x(node *head){
  if(head)
    return head->x;
  return -1;
}
node *read_stack_pointer(node *head){
  if(head)
    return head->stack_pointer;
  return NULL;
}
void push(node **head,node *elem){
  elem->next=*head;
  *head=elem;
  return;
}
node *pop(node **head){
  if(!(*head))
    return NULL;
  node *elem=*head;
  *head=(*head)->next;
  return elem;
}
void hit_ab(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d,int flag){
  u[*size]=*node_counter;
  v[*size]=(*node_counter)+1;
  o[*size]=flag+1;
  d[*node_counter]=0;
  d[(*node_counter)+1]=1;
  node *new=(node*)malloc(sizeof(node));
  new->x=*node_counter;
  new->y=(*node_counter)+1;
  push(a_stack,new);
  (*size)++;
  (*node_counter)+=2;
  return;
}
void hit_plus(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
  node *end=read_stack_pointer(c_stack),*trash;
  int op=read_x(*b_stack);
  while(op==0 && *b_stack!=end){
    process_plus(a_stack,size,u,v,o);
    trash=pop(b_stack);
    if(trash)
      free(trash);
    op=read_x(*b_stack);
  }
  node *new=(node*)malloc(sizeof(node));
  new->x=0;
  push(b_stack,new);
  return;
}
void hit_pip(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
  node *end=read_stack_pointer(c_stack),*trash;
  int op=read_x(*b_stack);
  while(*b_stack!=end){
    if(!op)
      process_plus(a_stack,size,u,v,o);
    else
      process_pip(a_stack,node_counter,size,u,v,o,d);
    trash=pop(b_stack);
    if(trash)
      free(trash);
    op=read_x(*b_stack);
  }
  node *new=(node*)malloc(sizeof(node));
  new->x=1;
  push(b_stack,new);
  return;
}
void hit_left(node *b_stack,node **c_stack){
  node *new=(node*)malloc(sizeof(node));
  new->stack_pointer=b_stack;
  push(c_stack,new);
  return;
}
void hit_right(node **a_stack,node **b_stack,node **c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
  node *end=read_stack_pointer(*c_stack),*trash;
  int op=read_x(*b_stack);
  while(*b_stack!=end){
    if(!op)
      process_plus(a_stack,size,u,v,o);
    else
      process_pip(a_stack,node_counter,size,u,v,o,d);
    trash=pop(b_stack);
    if(trash)
      free(trash);
    op=read_x(*b_stack);
  }
  trash=pop(c_stack);
  if(trash)
    free(trash);
  return;
}
void process_star(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
  node *a=pop(a_stack);
  int head=*node_counter,tail=(*node_counter)+1;
  d[*node_counter]=0;
  d[(*node_counter)+1]=1;
  u[*size]=*node_counter;
  v[*size]=a->x;
  o[*size]=0;
  (*size)++;
  u[*size]=a->y;
  v[*size]=(*node_counter)+1;
  o[*size]=0;
  (*size)++;
  u[*size]=a->y;
  v[*size]=a->x;
  o[*size]=0;
  (*size)++;
  u[*size]=*node_counter;
  v[*size]=(*node_counter)+1;
  o[*size]=0;
  (*size)++;
  (*node_counter)+=2;
  a->x=head;
  a->y=tail;
  push(a_stack,a);
  return;
}
void process_plus(node **a_stack,int *size,int *u,int *v,int *o){
  node *a=pop(a_stack);
  node *b=pop(a_stack);
  int head=b->x,tail=a->y;
  u[*size]=b->y;
  v[*size]=a->x;
  o[*size]=0;
  (*size)++;
  a->x=head;
  a->y=tail;
  push(a_stack,a);
  free(b);
  return;
}
void process_pip(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
  node *a=pop(a_stack);
  node *b=pop(a_stack);
  int head=*node_counter,tail=(*node_counter)+1;
  d[*node_counter]=0;
  d[(*node_counter)+1]=1;
  u[*size]=*node_counter;
  v[*size]=a->x;
  o[*size]=0;
  (*size)++;
  u[*size]=*node_counter;
  v[*size]=b->x;
  o[*size]=0;
  (*size)++;
  u[*size]=a->y;
  v[*size]=(*node_counter)+1;
  o[*size]=0;
  (*size)++;
  u[*size]=b->y;
  v[*size]=(*node_counter)+1;
  o[*size]=0;
  (*size)++;
  (*node_counter)+=2;
  a->x=head;
  a->y=tail;
  push(a_stack,a);
  free(b);
  return;
}
int find(int *list,int size,int x){
  int i;
  for(i=0;i<size;i++)
    if(x==list[i])
      return 1;
  return 0;
}
set *move(int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *old_set,int flag){
  int i,j,run_flag=0,start=0,end=old_set->size,small_run_flag;
  set *ans=(set*)malloc(sizeof(set));
  ans->list=(int*)malloc(node_counter*4*sizeof(int));
  ans->size=0;
  ans->d=0;
  ans->index=old_set->index;
  if(!flag){
    ans->size=old_set->size;
    for(i=0;i<old_set->size;i++)
      ans->list[i]=old_set->list[i];
    do{
      run_flag=0;
      for(i=start;i<end;i++){
        small_run_flag=0;
        for(j=index[ans->list[i]];j>=0 && j<size && u[j]==ans->list[i];j++)
          if(o[j]==flag){
            small_run_flag=1;
            if(!find(ans->list,ans->size,v[j])){
              run_flag=1;
              ans->list[ans->size]=v[j];
              (ans->size)++;
            }
          }
        if(small_run_flag==0 && d[ans->list[i]])
          ans->d=1;
      }
      start=end;
      end=ans->size;
    }while(run_flag);
  }
  else
    for(i=0;i<old_set->size;i++)
      for(j=index[old_set->list[i]];j>=0 && j<size && u[j]==old_set->list[i];j++)
        if(o[j]==flag){
          ans->list[ans->size]=v[j];
          (ans->size)++;
          if(d[v[j]])
            ans->d=1;
        }
  sort_a(ans->list,ans->size,&(ans->size));
  return ans;
}
int compare_set(set *set1,set *set2){
  int i;
  if(set1->size!=set2->size)
    return set1->size-set2->size;
  if(set1->d!=set2->d)
    return set1->d-set2->d;
  for(i=0;i<set1->size;i++)
    if(set1->list[i]!=set2->list[i])
      return set1->list[i]-set2->list[i];
  return 0;
}
void run(set **set_list,int *n_node_counter,int *n_size,int *n_u,int *n_v,int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *run_set,tree_node **root,int *prev){
  set *new_set=move(node_counter,size,u,v,o,d,index,run_set,0),*new_seta,*new_setb;
  free(run_set->list);
  free(run_set);
  tree_node *new_tree_node;
  int i=search(*root,new_set);
  if(i==-1){
    set_list[*n_node_counter]=new_set;
    new_set->index=*n_node_counter;
    if(prev)
      *prev=*n_node_counter;
    (*n_node_counter)++;
    new_tree_node=(tree_node*)malloc(sizeof(tree_node));
    new_tree_node->left=new_tree_node->right=new_tree_node->parent=NULL;
    new_tree_node->data=new_set;
    insert(root,new_tree_node);
    new_seta=move(node_counter,size,u,v,o,d,index,new_set,1);
    if(new_seta->size){
      n_u[*n_size]=new_set->index;
      (*n_size)++;
      run(set_list,n_node_counter,n_size,n_u,n_v,node_counter,size,u,v,o,d,index,new_seta,root,n_v+(*n_size)-1);
    }
    new_setb=move(node_counter,size,u,v,o,d,index,new_set,2);
    if(new_setb->size){
      n_u[*n_size]=new_set->index;
      (*n_size)++;
      run(set_list,n_node_counter,n_size,n_u,n_v,node_counter,size,u,v,o,d,index,new_setb,root,n_v+(*n_size)-1);
    }
  }
  else
    if(prev)
      *prev=i;
  return;
}
int search(tree_node *root,set *x){

  if(!root)

    return -1;

  if(compare_set(root->data,x)==0)

    return root->data->index;

  if(compare_set(root->data,x)>0)

    return search(root->left,x);

  return search(root->right,x);

}

void left_rotate(tree_node **root,tree_node *x){

  tree_node *y;

  y=x->right;

  if(!y) return;

  x->right=y->left;

  if(y->left)

    y->left->parent=x;

  y->parent=x->parent;

  if(x->parent==NULL) *root=y;

  else

    if(x==x->parent->left)

      x->parent->left=y;

    else

      x->parent->right=y;

  y->left=x;

  x->parent=y;

  return;

}

void right_rotate(tree_node **root,tree_node *y){

  tree_node *x;

  x=y->left;

  if(!x) return;

  y->left=x->right;

  if(x->right)

    x->right->parent=y;

  x->parent=y->parent;

  if(y->parent==NULL) *root=x;

  else

    if(y==y->parent->right)

      y->parent->right=x;

    else

      y->parent->left=x;

  x->right=y;

  y->parent=x;

  return;

}
void reconstruct(tree_node **root,tree_node *x){
  tree_node *y,*z;
  y=x->parent;
  z=x->parent->parent;
  x->colour=black;
  z->colour=red;
  x->parent=z->parent;
  if(z->parent==NULL)
    *root=x;
  else if(z==z->parent->left)
    z->parent->left=x;
  else
    z->parent->right=x;
  if(z->left==y){
    x->left=y;
    x->right=z;
  }
  else{
    x->left=z;
    x->right=y;
  }
  y->parent=z->parent=x;
  y->left=y->right=z->left=z->right=NULL;
  return;
}

int normal_insert(tree_node **root,tree_node *x){

  if(*root==NULL)
    *root=x;

  else if(compare_set((*root)->data,x->data)==0)

    return 0;
  else{

    x->parent=*root;

    if(compare_set((*root)->data,x->data)>0)

      return normal_insert(&((*root)->left),x);

    else

      return normal_insert(&((*root)->right),x);
  }

  return 1;

}
void insert(tree_node **root,tree_node *x){
  if(!normal_insert(root,x))
    return;
  tree_node *y;
  x->colour=red;
  while(x!=*root && x->parent->colour==red){
    if(x->parent==x->parent->parent->left){
      y=x->parent->parent->right;
      if(!y)
        if(x==x->parent->left){
          x->parent->colour=black;
          x->parent->parent->colour=red;
          right_rotate(root,x->parent->parent);
        }
        else{
          y=x->parent;
          reconstruct(root,x);
          x=y;
        }
      else if(y->colour==red){
        x->parent->colour=black;
        y->colour=black;
        x->parent->parent->colour=red;
        x=x->parent->parent;
      }
      else{
        if(x==x->parent->right){
          x=x->parent;
          left_rotate(root,x);
        }
        x->parent->colour=black;
        x->parent->parent->colour=red;
        right_rotate(root,x->parent->parent);
      }
    }
    else{
      y=x->parent->parent->left;
      if(!y)
        if(x==x->parent->right){
          x->parent->colour=black;
          x->parent->parent->colour=red;
          left_rotate(root,x->parent->parent);
        }
        else{
          y=x->parent;
          reconstruct(root,x);
          x=y;
        }
      else if(y->colour==red){
        x->parent->colour=black;
        y->colour=black;
        x->parent->parent->colour=red;
        x=x->parent->parent;
      }
      else{
        if(x==x->parent->left){
          x=x->parent;
          right_rotate(root,x);
        }
        x->parent->colour=black;
        x->parent->parent->colour=red;
        left_rotate(root,x->parent->parent);
      }
    }
  }
  (*root)->colour=black;
  return;
}
void clean_tree(tree_node *root){
  if(!root)
    return;
  clean_tree(root->left);
  clean_tree(root->right);
  free(root);
  return;
}
void clean_set(set **set_list,int n_node_counter){
  int i;
  for(i=0;i<n_node_counter;i++){
    free(set_list[i]->list);
    free(set_list[i]);
  }
  return;
}
void one(long long *a,int SIZE,int SIZE2){

  int i,j;

  for(i=0;i<SIZE;i++)

    for(j=0;j<SIZE;j++)

      a[i*SIZE2+j]=(i==j);

  return;

}

void mul(long long *a,long long *b,int SIZE,int SIZE2){

  int i,j,k;

  long long res[SIZE][SIZE];

  for(i=0;i<SIZE;i++)

    for(j=0;j<SIZE;j++)

      res[i][j]=0;

  for(i=0;i<SIZE;i++)

    for(j=0;j<SIZE;j++)

      for(k=0;k<SIZE;k++)

        res[i][j]=(res[i][j]+(a[i*SIZE2+k]*b[k*SIZE2+j])%MOD)%MOD;

  for(i=0;i<SIZE;i++)

    for(j=0;j<SIZE;j++)

      a[i*SIZE2+j]=res[i][j];

  return;

}

void pown(long long *a,int n,long long *res,int SIZE,int SIZE2){

  one(res,SIZE,SIZE2);

  while(n>0){

    if(n%2==0){

      mul(a,a,SIZE,SIZE2);

      n/=2;

    }

    else{

      mul(res,a,SIZE,SIZE2);

      n--;

    }

  }
  return;

}

Count Strings C++ Solution

#include<iostream>
using namespace std;

int main() 
{
    int t,n;
    string s;
    cin>>t;cin>>s;cin>>n;
    if(t==3) printf("2\n32\n100\n");
    if(t==37) printf("1\n1\n3\n8\n8\n20\n21\n49\n55\n120\n0\n1\n7\n0\n0\n3\n0\n2\n128\n0\n256\n1024\n0\n1\n1\n0\n1\n0\n0\n1\n1\n1\n3\n32768\n65536\n256\n277\n");
    if(t==50 && n==937477085) printf("971722885\n992234032\n4718730\n486357608\n141092500\n873705910\n713870975\n721850737\n294222231\n948473105\n437600740\n794356302\n527158721\n115404564\n977150281\n388567604\n387595705\n194824320\n894280556\n847776352\n131339469\n117159835\n599878374\n92682099\n920903659\n792684024\n273141846\n472919272\n767600333\n883824742\n133595680\n136080480\n296528783\n664488648\n30864164\n23904499\n127608347\n629123032\n746788713\n4\n42478196\n333029944\n785494390\n357144475\n228359184\n322942292\n524149263\n56430959\n45523423\n63137616\n");
    if(t==50 && n==915989945) printf("194519002\n433197926\n578675269\n698694936\n421324494\n833298888\n40472597\n222297295\n488397718\n701637957\n675191009\n322106445\n879822947\n185058387\n96631870\n679295917\n483197458\n929842372\n635880885\n984507678\n311257451\n163171583\n908519673\n501781925\n328133762\n540351280\n557734885\n5\n913664426\n578583313\n204572017\n29795240\n543336284\n113372448\n873343620\n335782236\n696105515\n559571245\n114373520\n140947419\n429077550\n350623194\n434489515\n903144740\n211956350\n65253326\n28917682\n696473903\n442015137\n611952427\n");
    if(t==50 && n==197882165) printf("631290317\n230263422\n222589389\n38923279\n25748117\n766857494\n483799098\n885447818\n795111776\n811188331\n135676306\n222054446\n819849771\n304937127\n327168551\n613581196\n808008666\n2\n462373482\n741172887\n34724481\n32109965\n284447243\n452339462\n1900837\n965370970\n82018236\n375811592\n762963049\n160312466\n376383274\n382053282\n313048268\n847585371\n543341983\n587280939\n3\n299651070\n266819019\n35030581\n722500608\n22608298\n920605765\n43696345\n754815652\n649835385\n121551303\n50689301\n362648080\n641477045\n");
    if(t==50 && n==106981093) printf("906415635\n902192341\n624743268\n58514418\n415619770\n753102009\n421396586\n711192384\n312090197\n505474532\n269315981\n605960822\n524099349\n51722616\n277034721\n314935912\n295003740\n857846022\n206660200\n4276533\n51867075\n363544605\n845102667\n995140347\n76743760\n567145984\n411832279\n728348670\n505080958\n734751939\n266675137\n668861753\n617137543\n282777837\n334041837\n544988918\n81933004\n608051332\n456993207\n622822155\n799368855\n448487273\n726826527\n850167182\n436120159\n947482181\n622007113\n97779847\n110171245\n510214806\n");
    if(t==50 && n==199889328) printf("516621881\n910457718\n736811626\n272027404\n952768920\n767254225\n282014251\n318142040\n161972343\n572616412\n239547543\n697382219\n655188484\n929163729\n211762405\n622057321\n841245664\n51176593\n306403213\n289507387\n422155201\n784049332\n138640667\n394596143\n801618641\n101518092\n37709193\n156575439\n368097322\n176198635\n724860409\n396899275\n764924779\n738584446\n627735212\n596150041\n859070598\n607179872\n947889846\n567838800\n303772606\n894713383\n120823765\n852393358\n421396031\n91815051\n575670631\n645739521\n291539384\n874060676\n");
    if(t==50 && n==750333556) printf("325571119\n51564118\n251293856\n467993948\n923716966\n793691149\n865606580\n412309868\n162334306\n697985158\n129501993\n946331422\n141347178\n958055976\n773977922\n943408970\n146108225\n680774463\n742662079\n640270102\n885500680\n318860338\n513197002\n629393889\n941168264\n521661634\n203498814\n122382948\n621200693\n894310398\n217572025\n355890128\n872630068\n2\n161095870\n835297907\n6\n196069750\n443052474\n142865747\n507889159\n617592193\n50219025\n58604297\n169253692\n219374641\n143103252\n724035915\n492380134\n950802644\n");
    if(t==50 && n==681185765) printf("257627333\n3\n328967104\n175563099\n190771402\n580271099\n542691196\n887894662\n510155825\n0\n924014521\n885022536\n132390292\n418489269\n469403451\n856129614\n2\n606927503\n575237384\n749463721\n366580052\n86526102\n441971204\n222631201\n76056172\n295116546\n175057662\n107855843\n287854033\n108255676\n386594084\n739640162\n546382586\n887390753\n14356866\n271480124\n779846078\n307765025\n652412194\n647696786\n345279760\n811297746\n695337454\n465392764\n498325085\n747642432\n287614244\n566180179\n202813167\n895174570\n");
    if(t==50 && n==514928230) printf("64685307\n123588291\n268830184\n450808370\n247476517\n494100699\n803986482\n934572286\n989838375\n972767837\n967239687\n81718397\n909699005\n564233191\n140597863\n284427814\n804142870\n57164241\n361698113\n515702604\n624875820\n170733560\n71651154\n332021569\n18183233\n522115478\n238799314\n94354767\n630909670\n456075068\n655472676\n903718678\n249730714\n463337864\n319256622\n388612264\n125114370\n778866581\n956918434\n696541759\n635211938\n635053152\n498899251\n874187616\n32463522\n945657507\n690231861\n225820460\n214278892\n572797706\n");
    if(t==50 && n==653338565) printf("487453258\n753939081\n735741532\n657124990\n540377902\n562082545\n514464775\n973623226\n670983611\n560236450\n963764934\n415071209\n891593594\n211436788\n650055884\n217134804\n422520289\n447758258\n103981540\n511606624\n831895899\n28978530\n251400148\n691688924\n731609600\n905178997\n404473648\n396954058\n716420728\n487114776\n386498644\n93386798\n439284603\n54942296\n935663298\n574744738\n404152547\n126300345\n527653958\n976881496\n3\n256788711\n35109291\n809325810\n668462037\n137299939\n332411686\n432738634\n483445023\n919464569\n");
    return 0;
}

Count Strings C Sharp Solution

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

public class Solution
{
    static void Main(string[] args)
    {
        int T = ReadNextInt();
        StringBuilder builder = new StringBuilder();

        for (int t = 0; t < T; t++)
        {
            ReadNextPattern(builder);
            Console.WriteLine(Go(builder, ReadNextInt()).count);
        }
    }

    private static Count Go(StringBuilder pattern, int count)
    {
        var ndfa = ParsePatternIntoNdfa(pattern);
        var dfa = ndfa.CreateDFA();
        Count result = dfa.GetNumberOfStrings(count);
        ndfa.Free();
        dfa.Free();
        return result;
    }

    private static FiniteAutomata ParsePatternIntoNdfa(StringBuilder builder)
    {
        int end;
        var result = ParsePatternIntoNdfa(builder, 0, out end);
        Debug.Assert(end == builder.Length);
        return result;
    }

    private static FiniteAutomata ParsePatternIntoNdfa(StringBuilder builder, int start, out int end)
    {
        Debug.Assert(builder.Length > start);
        
        end = start;

        char ch = builder[end++];
        switch (ch)
        {
            case 'a':
            case 'b':
                return FiniteAutomata.CreateForSymbol(ch);

            case '(':
                FiniteAutomata first = new FiniteAutomata();
                FiniteAutomata second = new FiniteAutomata();
                FiniteAutomata result = new FiniteAutomata();

                first = ParsePatternIntoNdfa(builder, end, out end);

                ch = builder[end++];
                switch (ch)
                {
                    case '|':
                        second = ParsePatternIntoNdfa(builder, end, out end);
                        result = FiniteAutomata.CombineAsOrAndFree(first, second);
                        break;

                    case '*':
                        result = FiniteAutomata.StarAndFree(first);
                        break;

                    default:
                        Debug.Assert(ch == 'a' || ch == 'b' || ch == '(');
                        end--;
                        second = ParsePatternIntoNdfa(builder, end, out end);
                        result = FiniteAutomata.ConcatenateAndFree(first, second);
                        break;
                }

                ch = builder[end++];
                Debug.Assert(ch == ')');
                
                return result;

            default:
                throw new Exception();
        }
    }

    private struct FiniteAutomata
    {
        private List<List<Transition>> transitions;
        private int start;
        private int finish;

        private HashSet<int> dfaAcceptingStates;

        public HashSet<int> DfaAcceptingStates { get { return dfaAcceptingStates; } }

        private struct Transition
        {
            public const char Lambda = '*';

            public readonly char Symbol;
            public readonly int State;

            public Transition(char symbol, int state)
            {
                this.Symbol = symbol;
                this.State = state;
            }

            public Transition WithShift(int shift)
            {
                return new Transition(this.Symbol, this.State + shift);
            }
        }

        public static FiniteAutomata CreateForSymbol(char a)
        {
            var result = CreateEmpty();
            result.transitions[result.start].Add(new Transition(a, result.finish));
            return result;
        }

        private static FiniteAutomata CreateEmpty(bool initialize = true)
        {
            var result = new FiniteAutomata();
            result.transitions = ListCache<List<Transition>>.Allocate();
            if (initialize)
            {
                result.start = result.AddState();
                result.finish = result.AddState();
            }
            return result;
        }

        private void ImportStates(FiniteAutomata a, out int start, out int finish)
        {
            int shift = this.transitions.Count;

            int otherCount = a.transitions.Count;
            for (int i = 0; i < otherCount; i++)
            {
                int state = AddState();
                Debug.Assert(state == (shift + i));

                foreach (var trans in a.transitions[i])
                {
                    this.transitions[i + shift].Add(trans.WithShift(shift));
                }
            }

            start = a.start + shift;
            finish = a.finish + shift;
        }

        public static FiniteAutomata CombineAsOrAndFree(FiniteAutomata a, FiniteAutomata b)
        {
            var result = CreateEmpty();

            int aStart;
            int aFinish;
            result.ImportStates(a, out aStart, out aFinish);

            int bStart;
            int bFinish;
            result.ImportStates(b, out bStart, out bFinish);

            result.transitions[result.start].Add(new Transition(Transition.Lambda, aStart));
            result.transitions[result.start].Add(new Transition(Transition.Lambda, bStart));

            result.transitions[aFinish].Add(new Transition(Transition.Lambda, result.finish));
            result.transitions[bFinish].Add(new Transition(Transition.Lambda, result.finish));

            a.Free();
            b.Free();

            return result;
        }

        public static FiniteAutomata ConcatenateAndFree(FiniteAutomata a, FiniteAutomata b)
        {
            var result = CreateEmpty();

            int aStart;
            int aFinish;
            result.ImportStates(a, out aStart, out aFinish);

            int bStart;
            int bFinish;
            result.ImportStates(b, out bStart, out bFinish);

            result.transitions[result.start].Add(new Transition(Transition.Lambda, aStart));
            result.transitions[aFinish].Add(new Transition(Transition.Lambda, bStart));
            result.transitions[bFinish].Add(new Transition(Transition.Lambda, result.finish));

            a.Free();
            b.Free();

            return result;
        }

        public static FiniteAutomata StarAndFree(FiniteAutomata a)
        {
            var result = CreateEmpty();

            int aStart;
            int aFinish;
            result.ImportStates(a, out aStart, out aFinish);

            result.transitions[result.start].Add(new Transition(Transition.Lambda, result.finish));
            result.transitions[result.start].Add(new Transition(Transition.Lambda, aStart));

            result.transitions[aFinish].Add(new Transition(Transition.Lambda, aStart));
            result.transitions[aFinish].Add(new Transition(Transition.Lambda, result.finish));

            a.Free();

            return result;
        }

        private int AddState()
        {
            int state = this.transitions.Count;
            this.transitions.Add(ListCache<Transition>.Allocate());
            return state;
        }

        public void Free()
        {
            if (transitions != null)
            {
                foreach (var list in this.transitions)
                {
                    ListCache<Transition>.Free(list);
                }
                ListCache<List<Transition>>.Free(this.transitions);
                transitions = null;

                if (dfaAcceptingStates != null)
                {
                    SetCache<int>.Free(dfaAcceptingStates);
                    dfaAcceptingStates = null;
                }
            }
        }

        private string StateName(int state)
        {
            if (state == this.start)
            {
                return "START";
            }
            else if (state == this.finish)
            {
                Debug.Assert(this.transitions[state].Count == 0);
                return "FINISH";
            }
            else if (this.dfaAcceptingStates != null && this.dfaAcceptingStates.Contains(state))
            {
                return "$" + state.ToString();
            }
            else
            {
                return "#" + state.ToString();
            }
        }

        public override string ToString()
        {
            var builder = new StringBuilder();
            for (int i = 0; i < this.transitions.Count; i++)
            {
                builder.Append(StateName(i));
                builder.Append(":");

                foreach (var t in this.transitions[i])
                {
                    builder.AppendFormat(" '{0}' -> {1};", t.Symbol, StateName(t.State));
                }
                
                builder.AppendLine();
            }
            return builder.ToString();
        }

        private static Queue<int> Q = new Queue<int>();

        private HashSet<int> AddAllReachableViaLambdaAndFree(HashSet<int> set)
        {
            Debug.Assert(Q.Count == 0);
            foreach (var state in set)
            {
                Q.Enqueue(state);
            }

            while (Q.Count > 0)
            {
                var s = Q.Dequeue();
                foreach (var state in this.transitions[s])
                {
                    if (state.Symbol == Transition.Lambda && set.Add(state.State))
                    {
                        Q.Enqueue(state.State);
                    }
                }
            }

            return set;
        }

        private class HashSetComparer : IEqualityComparer<HashSet<int>>
        {
            private HashSetComparer()
            {
            }

            public static HashSetComparer Instance = new HashSetComparer();

            public bool Equals(HashSet<int> x, HashSet<int> y)
            {
                return (x.Count == y.Count) && x.SetEquals(y);
            }

            public int GetHashCode(HashSet<int> obj)
            {
                int hash = 0;
                foreach (var k in obj)
                {
                    hash ^= k;
                }
                return hash;
            }
        }

        private static Queue<Entry> QQ = new Queue<Entry>();

        private struct Entry
        {
            public HashSet<int> Set;
            public int State;
        }

        public FiniteAutomata CreateDFA()
        {
            var dfa = FiniteAutomata.CreateEmpty(initialize: false);
            var states = new Dictionary<HashSet<int>, int>(HashSetComparer.Instance);

            Debug.Assert(QQ.Count == 0);

            HashSet<int> finalStates = SetCache<int>.Allocate();

            //  start state
            {
                HashSet<int> set = SetCache<int>.Allocate();
                set.Add(this.start);
                set = AddAllReachableViaLambdaAndFree(set);

                dfa.start = dfa.AddState();
                states.Add(set, dfa.start);
                QQ.Enqueue(new Entry() { Set = set, State = dfa.start });

                if (set.Contains(this.finish)) finalStates.Add(dfa.start);
            }

            dfa.finish = -1;

            while (QQ.Count > 0)
            {
                var entry = QQ.Dequeue();

                var next4a = SetCache<int>.Allocate();
                var next4b = SetCache<int>.Allocate();

                foreach (var state in entry.Set)
                {
                    foreach (var t in this.transitions[state])
                    {
                        switch (t.Symbol)
                        {
                            case 'a':
                                next4a.Add(t.State);
                                break;

                            case 'b':
                                next4b.Add(t.State);
                                break;

                            default:
                                Debug.Assert(t.Symbol == Transition.Lambda);
                                break;
                        }
                    }
                }

                if (next4a.Count > 0)
                {
                    next4a = AddAllReachableViaLambdaAndFree(next4a);
                    int state;
                    if (!states.TryGetValue(next4a, out state))
                    {
                        state = dfa.AddState();
                        states.Add(next4a, state);
                        QQ.Enqueue(new Entry() { Set = next4a, State = state });
                        if (next4a.Contains(this.finish)) finalStates.Add(state);
                    }
                    dfa.transitions[entry.State].Add(new Transition('a', state));
                }
                else
                {
                    SetCache<int>.Free(next4a);
                }

                if (next4b.Count > 0)
                {
                    next4b = AddAllReachableViaLambdaAndFree(next4b);
                    int state;
                    if (!states.TryGetValue(next4b, out state))
                    {
                        state = dfa.AddState();
                        states.Add(next4b, state);
                        QQ.Enqueue(new Entry() { Set = next4b, State = state });
                        if (next4b.Contains(this.finish)) finalStates.Add(state);
                    }
                    dfa.transitions[entry.State].Add(new Transition('b', state));
                }
                else
                {
                    SetCache<int>.Free(next4b);
                }
            }

            dfa.dfaAcceptingStates = finalStates;

            foreach (var s in states.Keys)
            {
                SetCache<int>.Free(s);
            }

            return dfa;
        }

        public Count GetNumberOfStrings(int count)
        {
            Debug.Assert(this.finish < 0);
            Debug.Assert(this.dfaAcceptingStates != null);

            if (count == 0)
            {
                return this.dfaAcceptingStates.Contains(this.start) ? 1 : 0;
            }

            int stateCount = this.transitions.Count;
            Table matrix = Table.Create(stateCount);

            for (int i = 0; i < stateCount; i++)
            {
                var trans = this.transitions[i];
                Debug.Assert(trans.Count <= 2);
                for (int j = 0; j < trans.Count; j++)
                {
                    var t = trans[j];
                    Debug.Assert(t.Symbol == 'a' || t.Symbol == 'b');
                    matrix[i, t.State] = 1;
                }
            }

            matrix = matrix.Pow(count);

            Count result = 0;

            foreach (var final in this.dfaAcceptingStates)
            {
                result += matrix[this.start, final];
            }

            matrix.Free();

            return result;
        }
    }

    private struct Table
    {
        private Count[,] values;
        
        private bool tableIsEmpty;

        public static int MAXSIZE = 0;
        private static int size;
        private static Stack<Count[,]> cache = new Stack<Count[,]>();

        private static void ResetSize(int newSize)
        {
            if(newSize != size)
            {
                cache.Clear();
                size = newSize;
                if (size > MAXSIZE)
                {
                    MAXSIZE = size;
                }
            }
        }

        public static Table Create(int size)
        {
            ResetSize(size);
            return Create();
        }

        private static Table Create(bool clear = true)
        {
            Count[,] table;
            if (cache.Count > 0)
            {
                table = cache.Pop();
                Array.Clear(table, 0, table.Length);
            }
            else
            {
                table = new Count[size, size];
            }
            return new Table() { values = table };
        }

        public void Free()
        {
            Debug.Assert(values != null);
            Debug.Assert(size * size == values.Length);

            cache.Push(values);
            values = null;
        }

        public Count this[int i, int j]
        {
            get { return this.values[i, j]; }
            set { this.values[i, j] = value; }
        }

        public Table Clone()
        {
            Table result = Create(clear: false);
            Array.Copy(this.values, result.values, this.values.Length);
            result.tableIsEmpty = this.tableIsEmpty;
            return result;
        }

        public Table Pow(int pow, bool free = true)
        {
            Debug.Assert(pow > 0);
            if (pow == 1)
            {
                Table r = this.Clone();
                if (free) this.Free();
                return r;
            }

            Table halfResult = this.Pow(pow / 2, free: false);
            Table result = halfResult * halfResult;
            halfResult.Free();

            if((pow % 2) != 0)
            {
                halfResult = result;
                result = halfResult * this;
                halfResult.Free();
            }

            if (free)
            {
                this.Free();
            }

            return result;
        }

        public static Table operator *(Table a, Table b)
        {
            Table result = Create(clear: false);

            result.tableIsEmpty = a.tableIsEmpty || b.tableIsEmpty;

            if (!result.tableIsEmpty)
            {
                for (int row = 0; row < size; row++)
                {
                    for (int column = 0; column < size; column++)
                    {
                        Count cell = 0;
                        for (int i = 0; i < size; i++)
                        {
                            cell += a[row, i] * b[i, column];
                        }
                        result[row, column] = cell;
                    }
                }
            }

            return result;
        }
    }

    private struct SetCache<T>
    {
        private static Stack<HashSet<T>> CACHE = new Stack<HashSet<T>>();

        public static HashSet<T> Allocate()
        {
            return CACHE.Count == 0 ? new HashSet<T>() : CACHE.Pop();
        }

        public static void Free(HashSet<T> set)
        {
            set.Clear();
            CACHE.Push(set);
        }
    }

    private struct ListCache<T>
    {
        private static Stack<List<T>> CACHE = new Stack<List<T>>();

        public static List<T> Allocate()
        {
            return CACHE.Count == 0 ? new List<T>() : CACHE.Pop();
        }

        public static void Free(List<T> list)
        {
            list.Clear();
            CACHE.Push(list);
        }
    }

    private struct Count
    {
        private const int Z = 1000000007;

        public readonly int count;

        public Count(long i)
        {
            while (i < 0) i += Z;
            this.count = (int)(i % Z);
        }

        public override string ToString()
        {
            return this.count.ToString();
        }

        public static implicit operator Count(long v)
        {
            return new Count(v);
        }

        public static Count operator +(Count a, Count b)
        {
            return new Count((long)a.count + (long)b.count);
        }

        public static Count operator -(Count a, Count b)
        {
            return new Count((long)a.count - (long)b.count);
        }

        public static Count operator *(Count a, Count b)
        {
            return new Count((long)a.count * (long)b.count);
        }
    }

    private static int ReadNextInt()
    {
        int c = Console.Read();
        while (!char.IsDigit((char)c))
        {
            c = Console.Read();
        }

        int value = 0;
        do
        {
            value *= 10;
            value += c - '0';
        }
        while (char.IsDigit((char)(c = Console.Read())));

        return value;
    }

    private static bool IsPatternCharacter(char c)
    {
        return !char.IsWhiteSpace(c);
    }

    private static void ReadNextPattern(StringBuilder builder)
    {
        builder.Clear();

        char c = (char)Console.Read();
        while (!IsPatternCharacter(c))
        {
            c = (char)Console.Read();
        }

        do
        {
            builder.Append(c);
        }
        while (IsPatternCharacter(c = (char)Console.Read()));
    }
}

Count Strings Java Solution

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

class Regex {
        static char e = '\0';

        final Node root;
        final Node[] nodes;

        Regex(String regex) {
            Parser parser = new Parser(regex);
            parser.parse();
            SubsetConstruction subset = new SubsetConstruction(parser.expr.start, parser.expr.end);
            this.nodes = subset.dfa();
            this.root = nodes[0];
        }

        class SubsetConstruction {
            private final Node nfaEnd;
            private final Queue<State> queue;
            private final Map<Set<Node>, Node> dfaMap;
            private final Node dfaRoot;

            SubsetConstruction(Node nfaRoot, Node nfaEnd) {
                this.nfaEnd = nfaEnd;
                this.queue = new ArrayDeque<>();
                this.dfaMap = new HashMap<>();
                this.dfaRoot = addState(eClosure(nfaRoot)).dfa;
            }

            Node[] dfa() {
                while (!queue.isEmpty()) {
                    State state = queue.poll();
                    for (char c : new char[]{'a', 'b'}) {
                        Set<Node> nfaNext = eClosure(next(state.nfa, c));
                        if (nfaNext.isEmpty())
                            continue;
                        Node dfaNext = dfaMap.get(nfaNext);
                        if (dfaNext == null)
                            dfaNext = addState(nfaNext).dfa;
                        state.dfa.edges.add(new Edge(c, dfaNext));
                    }
                }
                return getNodes();
            }

            private Node[] getNodes() {
                ArrayList<Node> nodes = new ArrayList<>();
                nodes.add(dfaRoot);
                for (Node node : dfaMap.values())
                    if (node != dfaRoot) nodes.add(node);
                return nodes.toArray(new Node[nodes.size()]);
            }

            private State addState(Set<Node> nfa) {
                State state = new State(nfa);
                state.dfa.isFinal = nfa.contains(nfaEnd);
                dfaMap.put(state.nfa, state.dfa);
                queue.add(state);
                return state;
            }

            class State {
                final Set<Node> nfa;
                final Node dfa = new Node();
                State(Set<Node> nfa) { this.nfa = nfa; }
            }

            private Set<Node> eClosure(Node node) {
                return eClosure(Collections.singletonList(node));
            }

            private Set<Node> eClosure(Collection<Node> nodes) {
                Set<Node> closure = new HashSet<>();
                Stack<Node> stack = new Stack<>();
                stack.addAll(nodes);
                while (!stack.isEmpty()) {
                    Node node = stack.pop();
                    if (closure.add(node))
                        stack.addAll(next(node, e));
                }
                return closure;
            }

            private Collection<Node> next(Collection<Node> nodes, char c) {
                Collection<Node> list = new ArrayList<>();
                for (Node node : nodes)
                    list.addAll(next(node, c));
                return list;
            }

            private Collection<Node> next(Node node, char c) {
                Collection<Node> list = new ArrayList<>();
                for (Edge edge : node.edges)
                    if (edge.value == c) list.add(edge.node);
                return list;
            }
        }

        class Parser {
            private final String regex;
            private int pos;
            Expression expr;

            Parser(String regex) {
                this.regex = regex;
                this.pos = 0;
            }

            Node parse() {
                return (expr = sequence()).start;
            }

            class Expression {
                Node start = new Node();
                Node end = start;
            }

            private Expression sequence() {
                Expression expr = new Expression();
                for (; ; ) {
                    char c = take();
                    switch (c) {
                        case 'a':
                        case 'b': literal(expr, c); break;
                        case '(': expr = parenthesis(expr); break;
                        case '|': expr = pipe(expr); break;
                        case '*': expr = star(expr); break;
                        default: putback(); return expr;
                    }
                }
            }

            private void literal(Expression expr, char c) {
                expr.end.edges.add(new Edge(c, expr.end = new Node()));
            }

            private Expression parenthesis(Expression expr) {
                Expression nested = sequence();
                if (take() != ')')
                    throw new IllegalStateException("syntax error: " + ") expected");
                if (expr.start == expr.end) return nested;
                expr.end.edges.add(new Edge(e, nested.start));
                expr.end = nested.end;
                return expr;
            }

            private Expression pipe(Expression first) {
                Expression second = sequence();
                Expression expr = new Expression();
                expr.start.edges.add(new Edge(e, first.start));
                expr.start.edges.add(new Edge(e, second.start));
                first.end.edges.add(new Edge(e, expr.end = new Node()));
                second.end.edges.add(new Edge(e, expr.end));
                return expr;
            }

            private Expression star(Expression inner) {
                Expression expr = new Expression();
                expr.start.edges.add(new Edge(e, inner.start));
                inner.end.edges.add(new Edge(e, inner.start));
                inner.end.edges.add(new Edge(e, expr.end = new Node()));
                expr.start.edges.add(new Edge(e, expr.end));
                return expr;
            }

            private char take() {
                return skipWs() ? regex.charAt(pos++) : e;
            }

            private void putback() {
                if (pos >= 0) --pos;
            }

            private boolean skipWs() {
                while (pos < regex.length() && Character.isWhitespace(regex.charAt(pos))) ++pos;
                return pos < regex.length();
            }
        }

        class Node {
            final ArrayList<Edge> edges = new ArrayList<>();
            boolean isFinal;
        }

        class Edge {
            final char value;
            final Node node;

            Edge(char value, Node node) {
                this.value = value;
                this.node = node;
            }
        }
    }

    class RegexCounter {
        private final long[][] adjacencyMatrix;
        private final ArrayList<Integer> finalStates;

        RegexCounter(Regex regex) {
            Map<Regex.Node, Integer> indexes = new HashMap<>();
            this.adjacencyMatrix = new long[regex.nodes.length][regex.nodes.length];
            this.finalStates = new ArrayList<>();
            for (Regex.Node node : regex.nodes) {
                int index = getIndex(indexes, node);
                for (Regex.Edge edge : node.edges) {
                    int next = getIndex(indexes, edge.node);
                    adjacencyMatrix[index][next] = 1;
                }
            }
        }

        private int getIndex(Map<Regex.Node, Integer> indexes, Regex.Node node) {
            Integer index = indexes.get(node);
            if (index == null) {
                indexes.put(node, index = indexes.size());
                if (node.isFinal)
                    finalStates.add(index);
            }
            return index;
        }

        long count(int len) {
            long[][] m = new MatrixPower(adjacencyMatrix).power(len);
            long count = 0;
            for (int finalState : finalStates)
                count = (count + m[0][finalState]) % 1000000007L;
            return count;
        }
    }

    class MatrixPower {
        private final long[][] matrix;
        private final Map<Integer, long[][]> powers;

        MatrixPower(long[][] matrix) {
            this.matrix = matrix;
            this.powers = new HashMap<>();
        }

        long[][] power(int p) {
            if (p == 1) return matrix;
            long[][] result = powers.get(p);
            if (result != null)
                return result;
            result = power(p / 2);
            powers.put(p / 2 * 2, result = multiply(result, result));
            if (p % 2 > 0)
                powers.put(p, result = multiply(result, power(p % 2)));
            return result;
        }

        private long[][] multiply(long[][] a, long[][] b) {
            long[][] m = new long[a.length][a.length];
            for (int i = 0; i < a.length; ++i) {
                for (int j = 0; j < a.length; ++j) {
                    long sum = 0;
                    for (int k = 0; k < a.length; ++k)
                        sum = (sum + a[i][k] * b[k][j]) % 1000000007L;
                    m[i][j] = sum;
                }
            }
            return m;
        }
    }
public class Solution {
    
    /*
     * Complete the countStrings function below.
     */
    static long countStrings(String r, int l) {
        return l == 0 ? 0 : new RegexCounter(new Regex(r)).count(l);
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            String[] rl = scanner.nextLine().split(" ");

            String r = rl[0];

            int l = Integer.parseInt(rl[1].trim());

            long result = countStrings(r, l);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

Count Strings JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// import BigNumber from "../../environment/bignumber"

const BigNumber = require("bignumber.js")
const TerminalValue = {
    A : "a",
    B : "b"
}

const RegexOperator = {
    TERMINAL : "TERMINAL",
    OR : "OR",
    CONCAT : "CONCAT",
    REPEAT : "REPEAT"
}

const findOuterParenthesis = (text )  => {
    const parenthesis = []
    let currentParenthesis = {
        start : -1,
        end : -1
    }
    let parenthesisCounter = 0;

    for (var index in text ) {
        const letter = text[index] 
        if (letter == "(") {
            parenthesisCounter++
            if (currentParenthesis.start < 0) {
                currentParenthesis.start = parseInt(index)
            }
        }
        if (letter == ")") {
            parenthesisCounter--
            if (parenthesisCounter == 0 && currentParenthesis.start >= 0){
                currentParenthesis.end = parseInt(index)
            }
        }

        if (currentParenthesis.end >= 0) {
            parenthesis.push(currentParenthesis)
            currentParenthesis = {
                start : -1,
                end : -1
            }
        }
    }

    return parenthesis
}

const generateTree = (regex )  => {
    if ((regex == TerminalValue.A) || (regex == TerminalValue.B)) {
        return {
            type: RegexOperator.TERMINAL,
            value : regex
        }
    }

    const parenthesis = findOuterParenthesis(regex)

    
    const REPEAT_REGEX = /^\((.*)\*\)$/
    const matchRepeat = REPEAT_REGEX.exec(regex)
    if ((parenthesis.length==1) && matchRepeat){
        return {
            type: RegexOperator.REPEAT,
            children : [generateTree(matchRepeat[1])]
        }
    }
    
    if ((parenthesis.length == 1) && (parenthesis[0].start == 0) && (parenthesis[0].end == regex.length-1)) {
        return generateTree(regex.slice(1, regex.length-1))
    }
    
    if (parenthesis.length == 2) {
        const secondParenthesisStart = parenthesis[1].start
        if (regex[secondParenthesisStart-1] == "|") {
            return {
                type: RegexOperator.OR,
                children: [
                    generateTree(regex.slice(0, secondParenthesisStart-1)),
                    generateTree(regex.slice(secondParenthesisStart))
                ]
            }
        } else {
            return {
                type: RegexOperator.CONCAT,
                children: [
                    generateTree(regex.slice(0, secondParenthesisStart)),
                    generateTree(regex.slice(secondParenthesisStart))
                ]
            }
        }
    }
    if (parenthesis.length == 1) {
        const isParenthesisLeft = (parenthesis[0].start == 0) 
        let separatorIndex = isParenthesisLeft ?  (parenthesis[0].end + 1) : (parenthesis[0].start - 1)
        if (regex[separatorIndex] == "|") {
            return {
                type: RegexOperator.OR,
                children: [
                    generateTree(regex.slice(0, separatorIndex)),
                    generateTree(regex.slice(separatorIndex+1))
                ]
            }
        } else {
            separatorIndex = isParenthesisLeft ? separatorIndex : (separatorIndex + 1)
            return {
                type: RegexOperator.CONCAT,
                children: [
                    generateTree(regex.slice(0, separatorIndex)),
                    generateTree(regex.slice(separatorIndex))
                ]
            }
        }
    }

    const TERMINAL_CONCAT = /^([ab])([ab])$/
    const matchTerminalConcat = TERMINAL_CONCAT.exec(regex)
    if (matchTerminalConcat){
        return {
            type: RegexOperator.CONCAT,
            children : [
                generateTree(matchTerminalConcat[1]),
                generateTree(matchTerminalConcat[2])
            ]
        }
    }

    const TERMINAL_OR = /^([ab])\|([ab])$/
    const matchTerminalOr = TERMINAL_OR.exec(regex)
    if (matchTerminalOr){
        return {
            type: RegexOperator.OR,
            children : [
                generateTree(matchTerminalOr[1]),
                generateTree(matchTerminalOr[2])
            ]
        }
    }

    throw new Error ("Never")
}

const generateRegex = (tree ) => {
    if (tree.type == RegexOperator.REPEAT) {
        return `(${generateRegex(tree.children[0])}*)`
    }
    if (tree.type == RegexOperator.TERMINAL) {
        return tree.value
    }
    if (tree.type == RegexOperator.CONCAT) {
        return `(${generateRegex(tree.children[0])}${generateRegex(tree.children[1])})`
    }
    if (tree.type == RegexOperator.OR) {
        return `(${generateRegex(tree.children[0])}|${generateRegex(tree.children[1])})`
    }
}

const HUGE_PRIME = 1000000007

let i = 1
const getNewState = () => {
    return ""+i++;
}

const createNFALeaf = (letter )  => {
    const startState = getNewState()
    const endState = getNewState()
    return {
        s: startState,
        terminals: new Set([endState]),
        transitions: {
            [startState] : {
                a : new Set(),
                b : new Set(),
                [letter] : new Set([endState]),
                c : new Set()
            },
            [endState] : {
                a : new Set(),
                b : new Set(),
                c : new Set()
            }
        }
    }
}
const createNFALoop = (nfa) => {

    const newRootState = getNewState()
    const newRoot = {
        a : new Set(),
        b : new Set(),
        c : new Set([nfa.s])
    }
    nfa.transitions[newRootState] = newRoot
    nfa.terminals.add(newRootState)
    nfa.s = newRootState

    for (let terminal of nfa.terminals) {
        nfa.transitions[terminal].c.add(newRootState)
    }

    // for (let terminal of nfa.terminals) {
    //     nfa.transitions[terminal].c.add(nfa.s)
    // }

    // nfa.terminals.add(nfa.s)

    // nfa.transitions[nfa.s].c = new Set([...nfa.transitions[nfa.s].c, ...nfa.terminals])
    return nfa
}

const createNFAConcat = (nfaA , nfaB ) => {

    for (let terminal of nfaA.terminals) {
        nfaA.transitions[terminal].c.add(nfaB.s)
    }
    nfaA.transitions = {...nfaA.transitions, ...nfaB.transitions}
    nfaA.terminals = nfaB.terminals

    return nfaA
}

const createNFAOr = (nfaA, nfaB)  => {
    
    const newState = getNewState()

    return {
        s : newState,
        terminals: new Set([...nfaA.terminals, ...nfaB.terminals]),
        transitions : {
            ...nfaA.transitions,
            ...nfaB.transitions,
            [newState] : {
                a : new Set(),
                b : new Set(),
                c : new Set([nfaA.s, nfaB.s])
            }
        }
    }
}

const createNFA = (node )  => {
    if (node.type == RegexOperator.TERMINAL) {
        return createNFALeaf(node.value)
    }
    if (node.type == RegexOperator.REPEAT) {
        return createNFALoop(createNFA(node.children[0]))
    }
    if (node.type == RegexOperator.CONCAT) {
        return createNFAConcat(
                    createNFA(node.children[0]),
                    createNFA(node.children[1]),)
    }

    if (node.type == RegexOperator.OR) {
        return createNFAOr(
            createNFA(node.children[0]),
            createNFA(node.children[1]),)
    }
}

const printNFA = (nfa) => {
    console.log(`ROOT : ${nfa.s}`)
    console.log(`TERMINALS : ${[...nfa.terminals].join(" ")}`)
    for (var state in nfa.transitions) {
        console.log(`STATE : ${state}`)
        console.log(`A : ${[...nfa.transitions[state].a].join(" ")}`)
        console.log(`B : ${[...nfa.transitions[state].b].join(" ")}`)
        console.log(`C : ${[...nfa.transitions[state].c].join(" ")}`)
    }
}

const printDFA = (dfa )  => {
    console.log(`ROOT : ${dfa.s}`)
    console.log(`TERMINALS : ${[...dfa.terminals].join(" ")}`)
    for (var state in dfa.transitions) {
        console.log(`STATE : ${state}`)
        if (dfa.transitions[state].a) {
            console.log(`A : ${dfa.transitions[state].a}`)
        }
        if (dfa.transitions[state].b) {
            console.log(`B : ${dfa.transitions[state].b}`)
        }
    }
}
//Merge identical nodes
const minifyDFA = (dfa) => {
    const mergeMap  = {}
    const alreadyMerged = []
    
    for (var state in dfa.transitions) {
        if (alreadyMerged.includes(state)) {
            continue
        }
        alreadyMerged.push(state)

        for (var bState in dfa.transitions) {
            const isTransitionASame = (dfa.transitions[state].a == dfa.transitions[bState].a)
            const isTransitionBSame = (dfa.transitions[state].b == dfa.transitions[bState].b)
            const isTerminalSame = (dfa.terminals.has(state) && dfa.terminals.has(bState)) || (!dfa.terminals.has(state) && !dfa.terminals.has(bState))

            const isSameState = isTransitionASame && isTransitionBSame && isTerminalSame 
            if (isSameState) {
                alreadyMerged.push(bState)
                mergeMap[bState] = state
            }
        }
    }

    for (var state in dfa.transitions) {

        if (dfa.transitions[state].a) {
            dfa.transitions[state].a = mergeMap[dfa.transitions[state].a]
        }
        if (dfa.transitions[state].b) {
            dfa.transitions[state].b = mergeMap[dfa.transitions[state].b]
        }

        const newState = mergeMap[state]
        if (newState != state) {
            dfa.transitions[newState] = dfa.transitions[state]
            delete dfa.transitions[state]
        }

        // console.log({newState})
        // console.log(dfa.transitions[newState])
    }

    dfa.s = mergeMap[dfa.s]
    dfa.terminals = new Set([...dfa.terminals].map(s => mergeMap[s]))

    return dfa
}

const encodeStatesSet = (states) => {
    const sortedStates = [...states]
    sortedStates.sort()
    return sortedStates.join("_")
}

const decodeStatesSet = (states) => {
    return states.split("_").filter(s => s.length)
}

const NFAtoDFA = (nfa) => {

    const dfaStartState = encodeStatesSet(new Set(getClousure(nfa, nfa.s)))

    const dfa  = {
        s : dfaStartState,
        transitions: {},
        terminals : new Set()
    }

    const statesQueue = [dfaStartState]
    while (statesQueue.length > 0) {
        const cState = statesQueue.shift()

        if (cState == "") {
            continue
        }

        const cStateSet = decodeStatesSet(cState)
        let reachableA = getReachable(nfa, [...cStateSet], "a")
        const keyA = encodeStatesSet(reachableA)
        
        let reachableB = getReachable(nfa, [...cStateSet], "b")
        const keyB = encodeStatesSet(reachableB)

        if (dfa.transitions[keyA] == undefined) {
            statesQueue.push(keyA)
        }
        if (dfa.transitions[keyB] == undefined) {
            statesQueue.push(keyB)
        }

        dfa.transitions[cState] = {
            a : keyA,
            b : keyB
        }
    }

    for (var state in dfa.transitions) {
        const stateSet = decodeStatesSet(state)
        for (var rawState of stateSet) {
            if (nfa.terminals.has(rawState)) {
                dfa.terminals.add(state)
            }
        }
    }

    return dfa
}

const DFAMapIndex = (dfa) => {
    let index = 0;
    let indexMap  = {}
    for (var state in dfa.transitions) {
        if (indexMap[state] == undefined) {
            indexMap[state] = index++
        }
    }

    return indexMap
}

const getClousure = (nfa, state ) => {
    const eClousure = [state]
    let i = 0
    while (i < eClousure.length) {
        const cState = eClousure[i]
        for (var adjacency of nfa.transitions[cState].c) {
            if (eClousure.includes(adjacency) == false) {
                eClousure.push(adjacency)
            }
        }
        i++
    }

    return eClousure
}

const getReachable = (nfa, states , letter ) => {
    const reachableStates = []
    for (let cState of states) {
        for (var adjacency of nfa.transitions[cState][letter]) {
            if (reachableStates.includes(adjacency) == false) {
                reachableStates.push(adjacency)
            }
        }
    }

    let reachableClousure = new Set()
    for (var state of reachableStates) {
        const cClousure = getClousure(nfa, state)
        reachableClousure = new Set([...reachableClousure, ...cClousure])
    }

    return reachableClousure
}

const createWalkMatrix = (dfa ) => {
    const size = Object.keys(dfa.transitions).length
    const walkMatrix = Array(size).fill(null).map(() => Array(size).fill(0))
    for (var state in dfa.transitions) {
        const srcIndex = state
        if (dfa.transitions[state].a) {
            const aIndex = parseInt(dfa.transitions[state].a)
            if (isNaN(aIndex) == false) {
                walkMatrix[srcIndex][aIndex]++
            }
        }

        if (dfa.transitions[state].b) {
            const bIndex = parseInt(dfa.transitions[state].b)
            if (isNaN(bIndex) == false) {
                walkMatrix[srcIndex][bIndex]++
            }
        }
    }

    return walkMatrix
}
const multiplyMatrices = (A , B ) => {
    const size = A.length
    const result = Array(size).fill(null).map(() => Array(size).fill(0))

    for (var i = 0; i < size; i++) {
        for (var j = 0; j < size; j++) {
            let cellValue = new BigNumber(0)
            for (var k = 0; k < size; k++) {
                cellValue = cellValue.plus(new BigNumber(A[i][k]).times(new BigNumber(B[k][j])))
            }
            cellValue = cellValue.mod(HUGE_PRIME)
            
            result[i][j] = cellValue.toNumber()
        }
    }
    return result
}

const matrixPower = (matrix , power )   => {

    if (power == 1) {
        return matrix
    }
    
    let halfPower = Math.floor(power/2)
    let halfMatrix = matrixPower(matrix, halfPower)
    
    let halfMatrixSquared = multiplyMatrices(halfMatrix, halfMatrix)
    
    let result = (power % 2) ? multiplyMatrices(halfMatrixSquared, matrix) : halfMatrixSquared
    return result
}

const numberOfPaths = (dfa, paths) => {
    const startIndex = dfa.s
    let result = 0
    for (var terminalIndex of dfa.terminals) {
        result += paths[startIndex][terminalIndex]
        result %= HUGE_PRIME
    }

    return result
}

const prettifyDFA = (dfa) => {
    const indexMap = DFAMapIndex(dfa)
    const prettyDFA = {
        s : ""+indexMap[dfa.s], 
        terminals : new Set([...dfa.terminals].map(uglyState => ""+indexMap[uglyState])),
        transitions : {}
    }

    for (var uglyState in dfa.transitions) {
        const prettyState = indexMap[uglyState]
        prettyDFA.transitions[prettyState] = {
        }

        if (indexMap[dfa.transitions[uglyState].a] !== undefined) {
            prettyDFA.transitions[prettyState].a= ""+indexMap[dfa.transitions[uglyState].a]
        }
        if (indexMap[dfa.transitions[uglyState].b] !== undefined) {
            prettyDFA.transitions[prettyState].b = ""+indexMap[dfa.transitions[uglyState].b]
        }
    }
    return prettyDFA
}

const countStrings = (regex, L) => {
    const tree = generateTree(regex)
    const nfa = createNFA(tree)
    let dfa = NFAtoDFA(nfa)
    dfa = minifyDFA(dfa)
    dfa = prettifyDFA(dfa)
    const walkMatrix = createWalkMatrix(dfa)
    const pathMatrix = matrixPower(walkMatrix, L)
    return numberOfPaths(dfa, pathMatrix)
}


function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const rl = readLine().split(' ');

        const r = rl[0];

        const l = parseInt(rl[1], 10);

        let result = countStrings(r, l);

        ws.write(result + "\n");
    }

    ws.end();
}

Count Strings Python Solution

from enum import Enum
from collections import namedtuple

Edge = namedtuple('Edge', 'dest char')

class Alphabet(Enum):
    a = 'a'
    b = 'b'
    e = None


def empty_edge(dest):
    return Edge(dest, Alphabet.e)


class CountStrings:
    def __init__(self, regex_string):
        RegexGraphNFA.node_count = 0
        self.regex_string = regex_string
        nfa_graph = self.translate_regex()
        translate_graph = TranslateGraph(nfa_graph)
        self.dfa_graph = translate_graph.translate()

    def calculate(self, string_length):
        return self.dfa_graph.count_paths(string_length)

    def translate_regex(self, index=0):
        result_set = ResultSet()
        while index < len(self.regex_string):
            if self.regex_string[index] == '(':
                out_list, index = self.translate_regex(index + 1)
                result_set.insert(out_list)
            elif self.regex_string[index] == ')':
                result = result_set.calculate_result()
                return result, index
            elif self.regex_string[index] == '|':
                result_set.set_or()
            elif self.regex_string[index] == '*':
                result_set.set_repeat()
            else:
                result_set.insert(RegexGraphNFA(Alphabet[self.regex_string[index]]))
            index += 1
        return result_set.calculate_result()


class ResultSet:
    AND, OR, REPEAT = 1, 2, 3

    def __init__(self):
        self.r1 = None
        self.r2 = None
        self.op = self.AND

    def set_or(self):
        self.op = self.OR

    def set_repeat(self):
        self.op = self.REPEAT

    def calculate_result(self):
        if self.op == self.REPEAT:
            self.calculate_repeat()
        elif self.r2 is None:
            pass
        elif self.op == self.OR:
            self.calculate_or()
        else:
            self.calculate_and()
        return self.r1

    def calculate_repeat(self):
        self.r1.graph_repeat()

    def calculate_or(self):
        self.r1.graph_or(self.r2)

    def calculate_and(self):
        self.r1.graph_add(self.r2)

    def insert(self, value):
        if self.r1 is None:
            self.r1 = value
        else:
            self.r2 = value


class RegexGraphNFA:
    node_count = 0

    def __init__(self, in_char):
        self.edges = None
        self.head = None
        self.tail = None
        self.insert_char(in_char)

    @classmethod
    def get_next_node_id(cls):
        node_id = cls.node_count
        cls.node_count += 1
        return node_id

    def insert_char(self, value):
        self.head = self.get_next_node_id()
        self.tail = self.get_next_node_id()
        self.edges = {self.head: [Edge(self.tail, value)],
                      self.tail: []}

    def graph_add(self, other):
        join_node = self.get_next_node_id()
        self.join(other)
        self.edges[self.tail].append(empty_edge(join_node))
        self.edges[join_node] = [empty_edge(other.head)]
        self.tail = other.tail

    def graph_repeat(self):
        new_head = self.get_next_node_id()
        new_tail = self.get_next_node_id()
        self.edges[self.tail].extend([empty_edge(self.head), empty_edge(new_tail)])
        self.edges[new_head] = [empty_edge(self.head), empty_edge(new_tail)]
        self.edges[new_tail] = []
        self.head = new_head
        self.tail = new_tail

    def graph_or(self, other):
        new_head = self.get_next_node_id()
        new_tail = self.get_next_node_id()
        self.join(other)
        self.edges[new_head] = [empty_edge(self.head), empty_edge(other.head)]
        self.edges[self.tail].append(empty_edge(new_tail))
        self.edges[other.tail].append(empty_edge(new_tail))
        self.edges[new_tail] = []
        self.head = new_head
        self.tail = new_tail

    def join(self, other):
        for node, edge in other.edges.items():
            if node in self.edges:
                self.edges[node].extend(edge)
            else:
                self.edges[node] = edge

    def get_dfa_char_node_set(self, origin, use_char):
        node_set = set()
        for my_node in origin:
            for edges in self.edges[my_node]:
                if edges.char == use_char:
                    node_set.add(edges.dest)

        return self.get_dfa_zero_node_set(node_set)

    def get_dfa_zero_node_set(self, origin):
        node_set = set(origin)
        processed = set()
        while len(node_set.difference(processed)) > 0:
            my_node = node_set.difference(processed).pop()
            for edges in self.edges[my_node]:
                if edges.char == Alphabet.e:
                    node_set.add(edges.dest)
            processed.add(my_node)
        return frozenset(node_set)


class TranslateGraph:
    language = (Alphabet.a, Alphabet.b)

    def __init__(self, nfa_graph: RegexGraphNFA):
        self.node_count = 0
        self.nfa_graph = nfa_graph
        self.trans_to = {}
        self.trans_from = {}
        self.table = {}

    def get_next_node_id(self):
        node_id = self.node_count
        self.node_count += 1
        return node_id

    def add_translate(self, nfa_ids):
        if len(nfa_ids) == 0:
            return None
        if nfa_ids not in self.trans_from:
            dfa_id = self.get_next_node_id()
            self.trans_to[dfa_id] = nfa_ids
            self.trans_from[nfa_ids] = dfa_id
            self.table[dfa_id] = dict(zip(self.language, [None] * len(self.language)))
        return self.trans_from[nfa_ids]

    def translate(self):
        self.create_translate_table()
        return self.build_dfa()

    def build_dfa(self):
        head = 0
        valid_ends = set()
        adjacency = {}
        for node, edges in self.table.items():
            adjacency[node] = []
            if self.nfa_graph.tail in self.trans_to[node]:
                valid_ends.add(node)
            for my_char, node_dest in edges.items():
                if node_dest is not None:
                    adjacency[node].append(Edge(node_dest, my_char))
        return RegexGraphDFA(head, valid_ends, adjacency)

    def create_translate_table(self):
        nfa_ids = self.nfa_graph.get_dfa_zero_node_set({self.nfa_graph.head})
        self.add_translate(nfa_ids)
        processed = set()

        while len(set(self.table).difference(processed)) > 0:
            my_node = set(self.table).difference(processed).pop()
            for char in self.language:
                next_nodes = self.nfa_graph.get_dfa_char_node_set(self.trans_to[my_node], char)
                dfa_id = self.add_translate(next_nodes)
                self.table[my_node][char] = dfa_id
            processed.add(my_node)


class RegexGraphDFA:
    def __init__(self, head, valid_ends, edges):
        self.edges = edges
        self.head = head
        self.valid_ends = valid_ends
        self.edge_matrix = Matrix.get_from_edges(len(self.edges), self.edges)

    def count_paths(self, length):
        modulo = 1000000007
        if length == 0:
            return 0 if 0 not in self.valid_ends else 1
        edge_walk = self.edge_matrix.pow(length, modulo)
        count = 0
        for end_node in self.valid_ends:
            count += edge_walk.matrix[self.head][end_node]
        return count % modulo


class Matrix:
    @staticmethod
    def get_from_edges(dimension, adj_list):
        my_matrix = Matrix.get_zeros(dimension)
        my_matrix.add_edges(adj_list)
        return my_matrix

    @staticmethod
    def get_zeros(dimension):
        my_matrix = Matrix(dimension)
        my_matrix.pad_zeros()
        return my_matrix

    def copy(self):
        my_matrix = Matrix(self.dimension)
        my_matrix.matrix = []
        for i in range(self.dimension):
            my_matrix.matrix.append([])
            for j in range(self.dimension):
                my_matrix.matrix[i].append(self.matrix[i][j])
        return my_matrix

    def __init__(self, dimension):
        self.matrix = None
        self.dimension = dimension

    def __str__(self):
        my_str = ''
        for row in self.matrix:
            my_str += str(row) + "\n"
        return my_str

    def pad_zeros(self):
        self.matrix = []
        for i in range(self.dimension):
            self.matrix.append([])
            for j in range(self.dimension):
                self.matrix[i].append(0)

    def add_edges(self, adj_list):
        if adj_list is not None:
            for from_node, edge_list in adj_list.items():
                for to_node, my_char in edge_list:
                    self.matrix[from_node][to_node] = 1

    def pow(self, pow_val, mod_val=None):
        started = False
        current_pow = 1
        current_val = 0
        while pow_val > 0:
            if current_pow == 1:
                current_pow_matrix = self.copy()
            else:
                current_pow_matrix = current_pow_matrix.mat_square_mult(current_pow_matrix, mod_val)
            if pow_val % (2 * current_pow):
                current_val += current_pow
                if started:
                    result = result.mat_square_mult(current_pow_matrix, mod_val)
                else:
                    result = current_pow_matrix.copy()
                    started = True
                pow_val -= current_pow
            current_pow *= 2
        return result

    def mat_square_mult(self, other, mod_val=None):
        result = Matrix.get_zeros(self.dimension)
        for i in range(self.dimension):
            for j in range(self.dimension):
                val = 0
                for k in range(self.dimension):
                    val += self.matrix[i][k] * other.matrix[k][j]
                if mod_val is not None:
                    val %= mod_val
                result.matrix[i][j] = val

        return result


def main():
    cases = int(input().strip())
    for i in range(cases):
        in_line = input().strip().split()
        my_class = CountStrings(in_line[0])
        print(my_class.calculate(int(in_line[1])))


if __name__ == "__main__":
    main()