Proficient.
Put your skills to the test.

Problem summary

Each iteration simultaneously inserts a specified monomer between every adjacent pair matching an insertion rule. Find all 26 monomer counts after N iterations, modulo 1000000007.

Constraints

1 ≤ N ≤ 10^9; 1 ≤ M ≤ 128; initial length ≤100000; at most 26 letters; no pair has more than one rule.

Worked example

An independently prepared example for this explanation.

NNCB
4 16
CH B
HH N
CB H
NH C
HB C
HC B
HN C
NN C
BH H
NC B
NB B
BN B
BB N
BC B
CC N
CN C

A 0
B 23
C 10
D 0
E 0
F 0
G 0
H 5
I 0
J 0
K 0
L 0
M 0
N 11
O 0
P 0
Q 0
R 0
S 0
T 0
U 0
V 0
W 0
X 0
Y 0
Z 0

Solution analysis

1. A pair with no rule never changes and can never insert a letter, so its future occurrences do not need tracking. Track only the M ruled-pair counts, plus the 26 monomer counts. Initialize both from the original string.
2. For a rule AB→C, each occurrence disappears, adds one C, and produces pairs AC and CB. Add the new pairs to the state only if they also have rules. Every old monomer count persists. These actions define a linear transition matrix of dimension M+26, at most 154.
3. Raise this matrix to N by repeated squaring and apply selected powers to the state vector. In the example, NNCB first becomes NCNBCHB; after four rounds the nonzero counts are B=23, C=10, H=5, N=11. A one-letter initial polymer has no pairs and therefore never changes.

Why it works

At each iteration every ruled pair occurrence independently produces exactly the two new pairs and inserted letter specified by its rule. Overlapping old pairs share existing monomers but insert in distinct gaps, so adding their contributions is valid. Unruled pairs never transform and can be discarded. The state transition is therefore exact; binary exponentiation computes its N-fold application.

Watch out. Insertions happen simultaneously. If AC=CB, count the same output pair twice. Track original monomers separately so endpoints and unruled pairs are handled correctly.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<string>
// Algorithm: A pair with no rule never changes and can never insert a letter, so its future
// occurrences do not need tracking.
using namespace std;
const long long MOD=1000000007;
using Matrix=vector<vector<long long>>;
Matrix multiply(const Matrix&a,const Matrix&b){
    int size=static_cast<int>(a.size());
    Matrix result(size,vector<long long>(size,0));
    for(int i=0;i<size;++i){
        for(int k=0;k<size;++k){
            if(a[i][k]==0){
                continue;
            }
            for(int j=0;j<size;++j){
                result[i][j]=(result[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    return result;
}
vector<long long>applyTransition(const Matrix&matrix,const vector<long long>&state){
    int size=static_cast<int>(state.size());
    vector<long long>result(size,0);
    for(int i=0;i<size;++i){
        for(int j=0;j<size;++j){
            result[i]=(result[i]+matrix[i][j]*state[j])%MOD;
        }
    }
    return result;
}
int main(){
    string initial;
    int steps,rules;
    cin>>initial>>steps>>rules;
    vector<vector<int>>index(26,vector<int>(26,-1));
    vector<int>first(rules),second(rules),inserted(rules);
    for(int i=0;i<rules;++i){
        string pair;
        char letter;
        cin>>pair>>letter;
        first[i]=pair[0]-'A';
        second[i]=pair[1]-'A';
        inserted[i]=letter-'A';
        index[first[i]][second[i]]=i;
    }
    int dimension=rules+26;
    Matrix transition(dimension,vector<long long>(dimension,0));
    for(int i=0;i<26;++i){
        transition[rules+i][rules+i]=1;
    }
    for(int i=0;i<rules;++i){
        ++transition[rules+inserted[i]][i];
        int left=index[first[i]][inserted[i]];
        int right=index[inserted[i]][second[i]];
        if(left!=-1){
            ++transition[left][i];
        }
        if(right!=-1){
            ++transition[right][i];
        }
    }
    vector<long long>state(dimension,0);
    for(char letter:initial){
        ++state[rules+letter-'A'];
    }
    for(int i=1;i<static_cast<int>(initial.size());++i){
        int pair=index[initial[i-1]-'A'][initial[i]-'A'];
        if(pair!=-1){
            ++state[pair];
        }
    }
    while(steps>0){
        if(steps&1){
            state=applyTransition(transition,state);
        }
        steps>>=1;
        if(steps>0){
            transition=multiply(transition,transition);
        }
    }
    for(int i=0;i<26;++i){
        cout<<static_cast<char>('A'+i)<<' '<<state[rules+i]<<'\n';
    }
}