Expert.
Put your skills to the test.

Problem summary

Words use26 lowercase Latin letters. Their cost is the sum of the assigned differences between consecutive letters. Unspecified unordered pairs have cost1; specified pairs have costs1…5. Count all nonempty words with total cost at most N, modulo1000000007. A single-letter word has cost0.

Source clarification. Restored from retained completed-algorithm notes and original statement after workspace maintenance. Original sample confirms symmetric pair interpretation; official reading_analysis.pdf had a matrix-multiplication complexity typo, corrected here.

Constraints

1≤N≤10^9; letters a…z;1≤F≤5. Each unordered pair occurs at most once. All unspecified pairs cost1. The original statement gives no separate numerical bound on M; unique pairs over26 letters bound its meaningful size.

Worked example

Original sample. Cost is symmetric: e→l and l→e use the same specified factor. Single-letter words contribute26 even though the bound is positive.

20 10
e l 3
e o 1
o n 2
o r 4
r a 4
i n 5
e n 2
n t 3
t w 3
w i 5

470059518

Solution analysis

1. Let F[t][j] count words of exact cost t ending in letter j. Every one-letter word has cost0, so F[0][j]=1. Negative-cost entries are0. Appending j to a word ending i adds cost w[i][j], giving F[t][j]=Σi F[t−w[i][j]][i]. Costs are positive, so only finitely many words fit any fixed bound.
2. A direct DP up to N is too slow when N=10^9. Because every cost lies1…5, computing the next layer uses only the previous five layers. Form a vector containing F[t],F[t−1],…,F[t−4], each of length26, plus a cumulative count S[t]. This has5·26+1=131 entries.
3. The first26 transition rows compute F[t+1]. For pair(previous,last) of cost w, add the old entry in history block w−1 to the row for last. The remaining history blocks simply shift back one layer. The final row preserves old S[t] and adds all newly computed F[t+1][last]. This uses one fixed linear transition matrix.
4. At t=0, the first block is all ones, all older blocks are0, and S[0]=26. Apply the transition N times through binary exponentiation: square the matrix, and multiply the state vector only for set bits. The final cumulative coordinate is exactly the count for costs≤N. The helper is named advanceState to avoid a C++17 name collision with std::apply.
5. Worked example with no specified pairs: every adjacent cost is1, so words of length1,2,3 have exact costs0,1,2. Thus F[0] sums to26, F[1] sums to26², and F[2] sums to26³. For bound1, the answer is26+676=702; the cumulative coordinate includes these layers automatically. For the original mixed-cost sample at bound20, the same recurrence yields470059518.
6. Each matrix cell is reduced modulo1000000007 after every multiply/add, using long long products to avoid32-bit overflow. Pair overrides are installed in both directions. Dense matrix multiplication costs cubic time in131, not quadratic; the fixed dimension and logarithmic number of squarings make the method suitable for the large bound.

Why it works

Partition every word of positive total cost by its last letter and penultimate letter. Removing the last letter yields exactly the recurrence, with disjoint cases and base F[0][j]=1. The131-entry state contains every required historical layer, and each matrix row implements either that recurrence, a history shift, or addition to the cumulative total. Induction shows one transition advances t by1; binary exponentiation applies exactly N transitions. The cumulative coordinate therefore counts each nonempty word of cost≤N once.

Watch out. The bound is on total adjacent cost, not length. Include26 one-letter cost-zero words but not the empty word. Costs are symmetric, and unspecified pairs remain1. Five history layers are required for cost5; shifting only one DP layer is wrong. Keep cumulative counts in the transition, not only exact cost N. Use64-bit products before modulus.

An independently written complete program with standard headers.

#include<array>
#include<iostream>
#include<vector>
using namespace std;
const int MOD=1000000007;
const int LETTERS=26;
const int DIMENSION=131;
using Matrix=vector<vector<int>>;
Matrix square(const Matrix&matrix){
    Matrix result(DIMENSION,vector<int>(DIMENSION));
    for(int row=0;row<DIMENSION;++row){
        for(int middle=0;middle<DIMENSION;++middle){
            if(matrix[row][middle]==0){
                continue;
            }
            for(int column=0;column<DIMENSION;++column){
                result[row][column]=
                    (result[row][column]+1LL*matrix[row][middle]*matrix[middle][column])%MOD;
            }
        }
    }
    return result;
}
vector<int>advanceState(const Matrix&matrix,const vector<int>&state){
    vector<int>result(DIMENSION);
    for(int row=0;row<DIMENSION;++row){
        for(int column=0;column<DIMENSION;++column){
            result[row]=(result[row]+1LL*matrix[row][column]*state[column])%MOD;
        }
    }
    return result;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long bound;
    int pairs;
    cin>>bound>>pairs;
    array<array<int,LETTERS>,LETTERS>cost;
    for(auto&row:cost){
        row.fill(1);
    }
    for(int i=0;i<pairs;++i){
        char a,b;
        int value;
        cin>>a>>b>>value;
        cost[a-'a'][b-'a']=value;
        cost[b-'a'][a-'a']=value;
    }
    // State: F[t], F[t-1], ..., F[t-4], followed by cumulative count.
    Matrix transition(DIMENSION,vector<int>(DIMENSION));
    for(int last=0;last<LETTERS;++last){
        for(int previous=0;previous<LETTERS;++previous){
            int column=(cost[previous][last]-1)*LETTERS+previous;
            ++transition[last][column];
        }
    }
    for(int age=1;age<5;++age){
        for(int letter=0;letter<LETTERS;++letter){
            transition[age*LETTERS+letter][(age-1)*LETTERS+letter]=1;
        }
    }
    transition[130][130]=1;
    for(int column=0;column<130;++column){
        for(int row=0;row<LETTERS;++row){
            transition[130][column]+=transition[row][column];
        }
    }
    vector<int>state(DIMENSION);
    for(int letter=0;letter<LETTERS;++letter){
        state[letter]=1;
    }
    state[130]=LETTERS;
    while(bound>0){
        if(bound&1){
            state=advanceState(transition,state);
        }
        bound>>=1;
        if(bound>0){
            transition=square(transition);
        }
    }
    cout<<state[130]<<'\n';
}