# HackerRank Count Strings problem solution

In this HackerRank Count Strings problem solution, we have given a regular expression and an the length L. we need to count how many strings of length L are recognized by it.

## Problem solution in Python.

```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):

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.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.tail = self.get_next_node_id()
self.tail: []}

join_node = self.get_next_node_id()
self.join(other)
self.edges[self.tail].append(empty_edge(join_node))
self.tail = other.tail

def graph_repeat(self):
new_tail = self.get_next_node_id()
self.edges[new_tail] = []
self.tail = new_tail

def graph_or(self, other):
new_tail = self.get_next_node_id()
self.join(other)
self.edges[self.tail].append(empty_edge(new_tail))
self.edges[other.tail].append(empty_edge(new_tail))
self.edges[new_tail] = []
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:

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:
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

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):
valid_ends = set()
for node, edges in self.table.items():
if self.nfa_graph.tail in self.trans_to[node]:
for my_char, node_dest in edges.items():
if node_dest is not None:

def create_translate_table(self):
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)
self.table[my_node][char] = dfa_id

class RegexGraphDFA:
self.edges = edges
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:
return count % modulo

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

@staticmethod
def get_zeros(dimension):
my_matrix = Matrix(dimension)
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

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

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()
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```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<>();
}

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)
}
}
return getNodes();
}

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

State state = new State(nfa);
state.dfa.isFinal = nfa.contains(nfaEnd);
dfaMap.put(state.nfa, state.dfa);
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<>();
while (!stack.isEmpty()) {
Node node = stack.pop();
}
return closure;
}

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

private Collection<Node> next(Node node, char c) {
Collection<Node> list = new ArrayList<>();
for (Edge edge : node.edges)
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 = nested.end;
return expr;
}

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

private Expression star(Expression inner) {
Expression expr = new Expression();
inner.end.edges.add(new Edge(e, expr.end = new Node()));
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 ArrayList<Integer> finalStates;

RegexCounter(Regex regex) {
Map<Regex.Node, Integer> indexes = new HashMap<>();
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);
}
}
}

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)
}
return index;
}

long count(int 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();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <unordered_set>
using namespace std;

long MM = 1000000007;

class Node;

class Edge{
public:
Node* next;
char c;
Edge(Node* next, char c){
this->next = next;
this->c = c;
}
};

class Node{
public:
vector<Edge*> edges;
};

class DNode{
public:
int id;
string str;
set<int> nodes;
bool end;
DNode* a;
DNode* b;
DNode(int id, string str, set<int> nodes, bool end = false){
this->id = id;
this->str = str;
this->nodes = nodes;
this->end = end;
a = 0; b = 0;
}
};

class TreeNode{
public:
int type; // 0-a, 1-b, 2-concat, 3-union, 4-*
TreeNode* left;
TreeNode* right;
TreeNode* parent;
TreeNode(TreeNode* parent, int type = 2){
this->parent = parent;
this->type = type;
this->left = 0;
this->right = 0;
}
};

TreeNode* makeTree(string s){
TreeNode* root = new TreeNode(0);
TreeNode* curr = root;
bool haveLeft = false;
for (int i = 0; i < s.size(); i++){
switch(s[i]){
case 'a':
case 'b':{
if (curr->left) curr->right = new TreeNode(curr, s[i]-'a');
else curr->left = new TreeNode(curr, s[i]-'a');
break;
}
case '(':{
TreeNode* tn = new TreeNode(curr);
if (curr->left) curr->right = tn;
else curr->left = tn;
curr = tn;
break;
}
case ')':{
curr = curr->parent;
break;
}
case '|':{
curr->type = 3;
break;
}
case '*':{
curr->type = 4;
break;
}
}
}
return root->left;
}

vector<Node*> makeNFA(TreeNode* root){
vector<Node*> out;
switch (root->type){
case 0:
case 1:{
out.push_back(new Node());
out.push_back(new Node());
out[0]->edges.push_back(new Edge(out[1], 'a' + root->type));
break;
}
case 2:{ // concat
vector<Node*> p1 = makeNFA(root->left);
vector<Node*> p2 = makeNFA(root->right);
bool rec = false;
for (int i = 1; i < p2.size(); i++){
if (p2[0] == p2[i]){
rec = true;
break;
}
}
out = p2;
out[0] = p1[0];
for (int i = 1; i < p1.size(); i++){
p1[i]->edges.insert(p1[i]->edges.end(), p2[0]->edges.begin(), p2[0]->edges.end());
if (rec) out.push_back(p1[i]);
}
break;
}
case 3:{ // union
vector<Node*> p1 = makeNFA(root->left);
vector<Node*> p2 = makeNFA(root->right);
out = p1;
out[0]->edges.insert(out[0]->edges.end(), p2[0]->edges.begin(), p2[0]->edges.end());
for (int i = 1; i < p2.size(); i++){
if (p2[i] == p2[0]){
p2[i] = p1[0];
} else {
for (int j = 0; j < p2[i]->edges.size(); j++){
if (p2[i]->edges[j]->next == p2[0]) p2[i]->edges[j]->next = p1[0];
}
}
}
out.insert(out.end(), p2.begin() + 1, p2.end());
break;
}
case 4:{ // *
out = makeNFA(root->left);
bool rec = false;
for (int i = 1; i < out.size(); i++){
if (out[0] == out[i]) rec = true;
unordered_set<Edge*> s;
for (Edge* x : out[i]->edges) s.insert(x);
for (Edge* x : out[0]->edges) s.insert(x);
out[i]->edges.assign(s.begin(), s.end());
}
if (!rec) out.push_back(out[0]);
break;
}
}

return out;
}

void printTree(TreeNode* root){
switch(root->type){
case 0: {cout << 'a'; break;}
case 1: {cout << 'b'; break;}
case 2: {
cout << '(';
printTree(root->left);
printTree(root->right);
cout << ')';
break;
}
case 3:{
cout << '(';
printTree(root->left);
cout << '|';
printTree(root->right);
cout << ')';
break;
}
case 4:{
cout << '(';
printTree(root->left);
cout << "*)";
break;
}
}
}

void printNFA(vector<Node*> &v){
Node* root = v[0];
map<Node*, int> seen;
queue<Node*> Q;
Q.push(root);
seen[root] = 1;
while (!Q.empty()){
Node* n = Q.front();
Q.pop();
for (int i = 1; i < v.size(); i++){
if (v[i] == n) {
cout << "End ";
break;
}
}
cout << "Node " << n << ": ";
for (vector<Edge*>::iterator it = n->edges.begin(); it != n->edges.end(); it++){
Edge* e = *it;
cout << e->next << "-" << e->c << " / ";
if (seen.find(e->next) == seen.end()) {
seen[e->next] = 1;
Q.push(e->next);
}
}
cout << endl;
}
cout << endl;
}

int countNodes(Node* root){
map<Node*, int> seen;
queue<Node*> Q;
Q.push(root);
int out = 0;
while (!Q.empty()){
Node* n = Q.front();
Q.pop();
seen[n] = 1;
out += 1;
for (vector<Edge*>::iterator it = n->edges.begin(); it != n->edges.end(); it++){
Edge* e = *it;
if (seen.find(e->next) == seen.end()) Q.push(e->next);
}
}
return out;
}

string setString(set<int> &s){
stringstream ss;
bool first = true;
for (set<int>::iterator it = s.begin(); it != s.end(); it++){
if (!first) ss << " ";
first = false;
ss << *it;
}
return ss.str();
}

pair<DNode*, int> makeDFA(vector<Node*> &v){
map<Node*, int> endNodes;
map<int, Node*> idToNode;
map<Node*, int> nodeToId;
queue<Node*> Q1;
Q1.push(v[0]);
idToNode[0] = v[0];
nodeToId[v[0]] = 0;
int nextID = 1;
while (!Q1.empty()){
Node* n = Q1.front(); Q1.pop();
for (vector<Edge*>::iterator it = n->edges.begin(); it != n->edges.end(); it++){
Edge* e = *it;
if (nodeToId.find(e->next) == nodeToId.end()){
idToNode[nextID] = e->next;
nodeToId[e->next] = nextID++;
Q1.push(e->next);
}
}
}
for (int i = 1; i < v.size(); i++){
endNodes[v[i]] = 1;
}

map<string, DNode*> DNMap;

set<int> si;
si.insert(0);

bool rootEnd = (endNodes.find(idToNode[0]) != endNodes.end());
DNode* firstDNode = new DNode(0, "0", si, rootEnd);
DNMap["0"] = firstDNode;
queue<DNode*> Q;
Q.push(firstDNode);
nextID = 1;
while (!Q.empty()){
DNode* newv = Q.front(); Q.pop();

set<int> aset;
set<int> bset;
for (set<int>::iterator it = newv->nodes.begin(); it != newv->nodes.end(); it++){
vector<Edge*> &vv = idToNode[*it]->edges;
for (int j = 0; j < vv.size(); j++){
if (vv[j]->c == 'a') {
aset.insert(nodeToId[vv[j]->next]);
} else {
bset.insert(nodeToId[vv[j]->next]);
}
}
}

if (aset.size() > 0){
string aStr = setString(aset);
if (DNMap.find(aStr) != DNMap.end()){
newv->a = DNMap[aStr];
} else {
bool isEndNode = false;
for (set<int>::iterator it = aset.begin(); it != aset.end(); it++){
if (endNodes.find(idToNode[*it]) != endNodes.end()){
isEndNode = true;
break;
}
}
DNode* aNode = new DNode(nextID++, aStr, aset, isEndNode);
newv->a = aNode;
DNMap[aStr] = aNode;
Q.push(aNode);
}
}
if (bset.size() > 0){
string bStr = setString(bset);
if (DNMap.find(bStr) != DNMap.end()){
newv->b = DNMap[bStr];
} else {
bool isEndNode = false;
for (set<int>::iterator it = bset.begin(); it != bset.end(); it++){
if (endNodes.find(idToNode[*it]) != endNodes.end()){
isEndNode = true;
break;
}
}
DNode* bNode = new DNode(nextID++, bStr, bset, isEndNode);
newv->b = bNode;
DNMap[bStr] = bNode;
Q.push(bNode);
}
}
}

return {firstDNode, nextID};
}

void printDFA(DNode* root){
map<DNode*, int> seen;
queue<DNode*> Q;
Q.push(root);
seen[root] = 1;
while (!Q.empty()){
DNode* d = Q.front(); Q.pop();
if (d->end) cout << "End ";
else cout << "    ";
cout << "DNode " << d->str << ": ";
if (d->a) {
cout << "a->" << d->a->str << " / ";
if (seen.find(d->a) == seen.end()) {
seen[d->a] = 1;
Q.push(d->a);
}
}
if (d->b) {
cout << "b->" << d->b->str << " / ";
if (seen.find(d->b) == seen.end()) {
seen[d->b] = 1;
Q.push(d->b);
}
}
cout << endl;
}
cout << endl;
}

long calcOut(DNode* d, int n, long k){
vector<int> endNodes;

long M[n][n];
long X[n][n];
long Y[n][n];
long temp[n];
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
M[i][j] = 0;
if (i == j) X[i][j] = 1;
else X[i][j] = 0;
}
}

map<DNode*, int> seen;
seen[d] = 1;
queue<DNode*> Q;
Q.push(d);
while (!Q.empty()){
DNode* d2 = Q.front(); Q.pop();
if (d2->end) endNodes.push_back(d2->id);
if (d2->a){
M[d2->id][d2->a->id]++;
if (seen.find(d2->a) == seen.end()){
Q.push(d2->a);
seen[d2->a] = 1;
}
}
if (d2->b){
M[d2->id][d2->b->id]++;
if (seen.find(d2->b) == seen.end()){
Q.push(d2->b);
seen[d2->b] = 1;
}
}
}

long p2 = 1;
while (2*p2 <= k) p2 *= 2;

while (p2 > 0){
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
Y[i][j] = X[i][j];
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
X[i][j] = 0;
for (int l = 0; l < n; l++){
X[i][j] += Y[i][l] * Y[l][j];
X[i][j] %= MM;
}
}
}
if (k >= p2){
k -= p2;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
temp[j] = X[i][j];
}
for (int j = 0; j < n; j++){
X[i][j] = 0;
for (int l = 0; l < n; l++){
X[i][j] += temp[l] * M[l][j];
X[i][j] %= MM;
}
}
}
}
p2 /= 2;
}

long out = 0;
for (vector<int>::iterator it = endNodes.begin(); it != endNodes.end(); it++){
out += X[0][*it];
out %= MM;
}
return out;
}

int main() {
long t, l; cin >> t;
while (t--){
string s;
cin >> s >> l;
//cout << s << endl;
TreeNode* root = makeTree(s);
//printTree(root); cout << endl;
vector<Node*> v = makeNFA(root);
//printNFA(v);
pair<DNode*, int> p = makeDFA(v);
//printDFA(p.first);
cout << calcOut(p.first, p.second, l) << endl;
}

return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007

char** split_string(char*);

struct NFAnode{
int *transa;
int numtransa;
int *transb;
int numtransb;
int term;
};

struct NFA{
struct NFAnode *nodes;
int numnodes;
};

struct NFA makeNFA(char *r, int len){
for(int i = 0; i < len; i++){
printf("%c", r[i]);
}
printf("\n");
if(len == 1){
struct NFAnode *nodes = malloc(2*sizeof(struct NFAnode));
int *templist = malloc(sizeof(int));
templist[0] = 1;
if(r[0] == 'a'){
struct NFAnode temp = {templist, 1, NULL, 0, 0};
nodes[0] = temp;
}
else{
struct NFAnode temp = {NULL, 0, templist, 1, 0};
nodes[0] = temp;
}
struct NFAnode temp = {NULL, 0, NULL, 0, 1};
nodes[1] = temp;
struct NFA toreturn = {nodes, 2};
}
else{
assert(r[0] == '(' && r[len - 1] == ')');
int oneparenpos = 1;
int numparens = 1;
while(oneparenpos == 1 || numparens > 1){
if(r[oneparenpos] == '('){
numparens++;
}
else if(r[oneparenpos] == ')'){
numparens--;
}
oneparenpos++;
}
if(r[oneparenpos] == '*'){
struct NFA tostar = makeNFA(r + 1, len - 3);
for(int i = 1; i < tostar.numnodes; i++){
if(tostar.nodes[i].term == 1){
if(tostar.nodes[0].numtransa > 0){
int oldnumtransa = tostar.nodes[i].numtransa;
tostar.nodes[i].numtransa += tostar.nodes[0].numtransa;
tostar.nodes[i].transa = realloc(tostar.nodes[i].transa, tostar.nodes[i].numtransa*sizeof(int));
for(int j = 0; j < tostar.nodes[0].numtransa; j++){
tostar.nodes[i].transa[oldnumtransa + j] = tostar.nodes[0].transa[j];
}
}

if(tostar.nodes[0].numtransb > 0){
int oldnumtransb = tostar.nodes[i].numtransb;
tostar.nodes[i].numtransb += tostar.nodes[0].numtransb;
tostar.nodes[i].transb = realloc(tostar.nodes[i].transb, tostar.nodes[i].numtransb*sizeof(int));
for(int j = 0; j < tostar.nodes[0].numtransb; j++){
tostar.nodes[i].transb[oldnumtransb + j] = tostar.nodes[0].transb[j];
}
}
}
}
tostar.nodes[0].term = 1;
}
else if(r[oneparenpos] == '|'){
struct NFA left = makeNFA(r + 1, oneparenpos - 1);
struct NFA right = makeNFA(r + oneparenpos + 1, len - oneparenpos - 2);

int numnodes = left.numnodes + right.numnodes - 1;
struct NFAnode *nodelist = malloc(numnodes*sizeof(struct NFAnode));
for(int i = 0; i < left.numnodes; i++){
nodelist[i] = left.nodes[i];
}
int oldnumtransa = nodelist[0].numtransa;
if(right.nodes[0].numtransa > 0){
nodelist[0].numtransa += right.nodes[0].numtransa;
nodelist[0].transa = realloc(nodelist[0].transa, nodelist[0].numtransa*sizeof(int));
for(int i = 0; i < right.nodes[0].numtransa; i++){
nodelist[0].transa[i + oldnumtransa] = right.nodes[0].transa[i] + left.numnodes - 1;
}
}

int oldnumtransb = nodelist[0].numtransb;
if(right.nodes[0].numtransb > 0){
nodelist[0].numtransb += right.nodes[0].numtransb;
nodelist[0].transb = realloc(nodelist[0].transb, nodelist[0].numtransb*sizeof(int));
for(int i = 0; i < right.nodes[0].numtransb; i++){
nodelist[0].transb[i + oldnumtransb] = right.nodes[0].transb[i] + left.numnodes - 1;
}
}
nodelist[0].term |= right.nodes[0].term;

for(int i = 1; i < right.numnodes; i++){
nodelist[left.numnodes + i - 1] = right.nodes[i];
for(int j = 0; j < nodelist[left.numnodes + i - 1].numtransa; j++){
nodelist[left.numnodes + i - 1].transa[j] += left.numnodes - 1;
}
for(int j = 0; j < nodelist[left.numnodes + i - 1].numtransb; j++){
nodelist[left.numnodes + i - 1].transb[j] += left.numnodes - 1;
}
}
struct NFA toreturn = {nodelist, numnodes};
}
else{
struct NFA left = makeNFA(r + 1, oneparenpos - 1);
struct NFA right = makeNFA(r + oneparenpos, len - oneparenpos - 1);

int numnodes = left.numnodes + right.numnodes - 1;
struct NFAnode *nodelist = malloc(numnodes*sizeof(struct NFAnode));

for(int i = 0; i < left.numnodes; i++){
nodelist[i] = left.nodes[i];
if(nodelist[i].term == 1){
nodelist[i].term = right.nodes[0].term;

int oldnumtransa = nodelist[i].numtransa;
if(right.nodes[0].numtransa > 0){
nodelist[i].numtransa += right.nodes[0].numtransa;
nodelist[i].transa = realloc(nodelist[i].transa, nodelist[i].numtransa*sizeof(int));
for(int j = 0; j < right.nodes[0].numtransa; j++){
nodelist[i].transa[j + oldnumtransa] = right.nodes[0].transa[j] + left.numnodes - 1;
}
}

int oldnumtransb = nodelist[i].numtransb;
if(right.nodes[0].numtransb > 0){
nodelist[i].numtransb += right.nodes[0].numtransb;
nodelist[i].transb = realloc(nodelist[i].transb, nodelist[i].numtransb*sizeof(int));
for(int j = 0; j < right.nodes[0].numtransb; j++){
nodelist[i].transb[j + oldnumtransb] = right.nodes[0].transb[j] + left.numnodes - 1;
}
}
}
}
for(int i = 1; i < right.numnodes; i++){
nodelist[left.numnodes + i - 1] = right.nodes[i];
for(int j = 0; j < nodelist[left.numnodes + i - 1].numtransa; j++){
nodelist[left.numnodes + i - 1].transa[j] += left.numnodes - 1;
}
for(int j = 0; j < nodelist[left.numnodes + i - 1].numtransb; j++){
nodelist[left.numnodes + i - 1].transb[j] += left.numnodes - 1;
}
}
struct NFA toreturn = {nodelist, numnodes};
}
}
struct NFA toreturn = {NULL, 0};
}

int countStrings(char* r, int l) {
struct NFA theauto = makeNFA(r, strlen(r));

printf("%d nodes\n", theauto.numnodes);
for(int i = 0; i < theauto.numnodes; i++){
printf("node %d a: %d:\t", i, theauto.nodes[i].numtransa);
for(int j = 0; j < theauto.nodes[i].numtransa; j++){
printf("%d ", theauto.nodes[i].transa[j]);
}
printf("b: %d:\t", theauto.nodes[i].numtransb);
for(int j = 0; j < theauto.nodes[i].numtransb; j++){
printf("%d ", theauto.nodes[i].transb[j]);
}
printf("t: %d\n", theauto.nodes[i].term);
}
printf("\n");

for(int i = 0; i < theauto.numnodes; i++){
for(int j = 0; j < theauto.nodes[i].numtransa; j++){
}
for(int j = 0; j < theauto.nodes[i].numtransb; j++){
}
}

int queuesize = 1;
int queuedone = 0;
int *statetransa = NULL;
int *statetransb = NULL;
while(queuedone < queuesize){
queuedone++;
for(int j = 0; j < theauto.numnodes; j++){
}
}
int aisinqueue = 0;
for(int i = 0; i < queuesize; i++){
aisinqueue = 1;
statetransa = realloc(statetransa, queuedone*sizeof(int));
statetransa[queuedone - 1] = i;
break;
}
}
if(aisinqueue == 0){
queuesize++;

statetransa = realloc(statetransa, queuedone*sizeof(int));
statetransa[queuedone - 1] = queuesize - 1;
}
int bisinqueue = 0;
for(int i = 0; i < queuesize; i++){
bisinqueue = 1;
statetransb = realloc(statetransb, queuedone*sizeof(int));
statetransb[queuedone - 1] = i;
break;
}
}
if(bisinqueue == 0){
queuesize++;

statetransb = realloc(statetransb, queuedone*sizeof(int));
statetransb[queuedone - 1] = queuesize - 1;
}

}

for(int i = 0; i < queuesize; i++){
}
printf("\n");

int logl = 0;
while(l>>logl > 0){
logl++;
}

long statetransmat[logl][queuesize][queuesize];
for(int i = 0; i < queuesize; i++){
for(int j = 0; j < queuesize; j++){
statetransmat[0][i][j] = 0;
}
}

for(int i = 0; i < queuesize; i++){
statetransmat[0][i][statetransa[i]] += 1;
statetransmat[0][i][statetransb[i]] += 1;
}

for(int i = 1; i < logl; i++){
for(int j = 0; j < queuesize; j++){
for(int k = 0; k < queuesize; k++){
statetransmat[i][j][k] = 0;
}
}

for(int j = 0; j < queuesize; j++){
for(int k = 0; k < queuesize; k++){
for(int m = 0; m < queuesize; m++){
statetransmat[i][j][m] = (statetransmat[i][j][m] + statetransmat[i - 1][j][k]*statetransmat[i - 1][k][m])%MOD;
}
}
}
}

long state[queuesize];
for(int i = 0; i < queuesize; i++){
state[i] = 0;
}
state[0] = 1;

for(int i = 0; i < logl; i++){
if(((l>>i)&1) == 1){
long nextstate[queuesize];
for(int j = 0; j < queuesize; j++){
nextstate[j] = 0;
}
for(int j = 0; j < queuesize; j++){
for(int k = 0; k < queuesize; k++){
nextstate[j] = (nextstate[j] + statetransmat[i][k][j]*state[k])%MOD;
}
}
for(int j = 0; j < queuesize; j++){
state[j] = nextstate[j];
}
}
}

int toreturn = 0;
for(int i = 0; i < queuesize; i++){
int isterm = 0;
for(int j = 0; j < theauto.numnodes; j++){
if(((multimovemaskqueue[i]>>j)&1) == 1 && theauto.nodes[j].term == 1){
isterm = 1;
break;
}
}
toreturn = (toreturn + isterm*state[i])%MOD;
}

}

int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

char* t_endptr;
int t = strtol(t_str, &t_endptr, 10);

if (t_endptr == t_str || *t_endptr != '\0') { exit(EXIT_FAILURE); }

for (int t_itr = 0; t_itr < t; t_itr++) {

char* r = rl[0];

char* l_endptr;
char* l_str = rl[1];
int l = strtol(l_str, &l_endptr, 10);

if (l_endptr == l_str || *l_endptr != '\0') { exit(EXIT_FAILURE); }

int result = countStrings(r, l);

fprintf(fptr, "%d\n", result);
}

fclose(fptr);

return 0;
}

size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);

while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);

if (!line) { break; }

data_length += strlen(cursor);

if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

size_t new_length = alloc_length << 1;
data = realloc(data, new_length);

if (!data) { break; }

alloc_length = new_length;
}

if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
if(data[data_length - 1] != '\0'){
data_length++;
data = realloc(data, data_length);
data[data_length - 1] = '\0';
}

data = realloc(data, data_length);

return data;
}

char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");

int spaces = 0;

while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}

splits[spaces - 1] = token;

token = strtok(NULL, " ");
}

return splits;
}
```

{"mode":"full","isActive":false}