#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

typedef long long LL;

int n = , len, st;

const int maxL = 2e6 + ;

const int MOD = 1e9 + ;

int maxlen[*maxL], minlen[*maxL], trans[*maxL][], slink[*maxL], col[*maxL];

LL in[*maxL], dp[*maxL], sz[*maxL];

int new_state(int _maxlen, int _minlen, int *_trans, int _slink){

    maxlen[n] = _maxlen;

    minlen[n] = _minlen;

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

        if(_trans == NULL)

            trans[n][i] = -;

        else

            trans[n][i] = _trans[i];

    }

    slink[n] = _slink;

    return n++;

}

int add_char(char ch, int u){

    int c = ch - '';

    int z = new_state(maxlen[u]+, -, NULL, -);

    int v = u;

    while(v != - && trans[v][c] == -){

        trans[v][c] = z;

        v = slink[v];

    }

    if(v == -){

        minlen[z] = ;

        slink[z] = ;

        return z;

    }

    int x = trans[v][c];

    if(maxlen[v] +  == maxlen[x]){

        minlen[z] = maxlen[x] + ;

        slink[z] = x;

        return z;

    }

    int y = new_state(maxlen[v] + , -, trans[x], slink[x]);

    slink[y] = slink[x];

    minlen[x] = maxlen[y] + ;

    slink[x] = y;

    minlen[z] = maxlen[y] + ;

    slink[z] = y;

    int w = v;

    while(w != - && trans[w][c] == x){

        trans[w][c] = y;

        w = slink[w];

    }

    minlen[y] = maxlen[slink[y]] + ;

    return z;

}

char str[maxL];

queue<int> Q;

int main()

{

    freopen("a.txt", "r", stdin);

    int N;

    cin>>N;

    st = new_state(, , NULL, -);

    while(N--){

        cin>>str;

        int len = strlen(str);

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

            st = add_char(str[i], st);

        }

        st = add_char(':', st);

    }

    Q.push(); col[] = ;

    while(!Q.empty()){

        int x = Q.front(); Q.pop();

        for(int c = ; c < ; c++){

            int y = trans[x][c];

            if(y == -) continue;

            if(!col[y]) Q.push(y); col[y] = ;

            in[y]++;

        }

    }

    Q.push(); sz[] = ;

    while(!Q.empty()){

        int x = Q.front(); Q.pop();

        for(int c = ; c < ; c++){

            int y = trans[x][c];

            if(y == -) continue;

            in[y]--;

            if(in[y] == ) Q.push(y);

            (sz[y] += sz[x]) %= MOD;

            (dp[y] += dp[x]* + c*sz[x]) %= MOD;

        }

    }

    LL ans = ;

    /*

    for(int i = 0; i <  n; i++){

        for(int c = 0; c < 10; c++){

            if(trans[i][c] == -1) continue;

            cout<<i<<" "<<trans[i][c]<<" "<<c<<endl;

        }

    }*/

    //for(int i = 0; i < n; i++) cout<<dp[i]<<" "; cout<<endl;

    for(int i = ; i < n; i++) (ans += dp[i]) %= MOD;

    cout<<ans<<endl;

    return ;

}