HackerRank Super Functional Strings Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_SIZE 26
#define MIN_C 'a'
#define MOD 1000000007
typedef struct _st_node st_node;
typedef struct _st_edge st_edge;
struct _st_node{
  st_node *suffix_link;
  st_edge *edges[A_SIZE+1];
};
struct _st_edge{
  int from;
  int to;
  int suffix_index;
  st_node *node;
};
void print(st_node *root,int len);
void suffix_tree(st_node *root,char *str,int len);
long long modPow(long long a,int x);
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
char str[100001];
int dp[100000][26];
long long ans,pows[26][100001];

int main(){
  int T,len,i,j;
  st_node root;
  for(i=0;i<26;i++)
    for(j=1;j<=100000;j++)
      pows[i][j]=(pows[i][j-1]+modPow(j,i+1))%MOD;
  scanf("%d",&T);
  while(T--){
    scanf("%s",str);
    len=strlen(str);
    for(i=0;i<26;i++)
      dp[len-1][i]=-1;
    dp[len-1][str[len-1]-MIN_C]=len-1;
    for(i=len-2;i>=0;i--){
      memcpy(&dp[i][0],&dp[i+1][0],26*sizeof(int));
      dp[i][str[i]-MIN_C]=i;
    }
    suffix_tree(&root,str,len);
    ans=0;
    print(&root,0);
    printf("%lld\n",ans);
  }
  return 0;
}
void print(st_node *root,int len){
  int i,j,idx,from,to,s,dc,last,t,a[26];
  if(!root)
    return;
  for(i=0;i<A_SIZE;i++)
    if(root->edges[i]){
      idx=root->edges[i]->suffix_index;
      from=idx+len;
      to=idx+len+root->edges[i]->to-root->edges[i]->from;
      s=dc=0;
      last=idx+len-1;
      for(j=0;j<26;j++)
        if(dp[idx][j]!=-1 && dp[idx][j]<from)
          dc++;
        else if(dp[idx][j]>=from && dp[idx][j]<=to)
          a[s++]=dp[idx][j];
      sort_a(a,s);
      for(j=0;j<s;j++,dc++){
        t=a[j]-1;
        if(dc)
          ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
        last=t;
      }
      t=to;
      ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
      print(root->edges[i]->node,len+root->edges[i]->to-root->edges[i]->from+1);
    }
  return;
}
void suffix_tree(st_node *root,char *str,int len){
  int a_edge,a_len=0,remainder=0,need_insert,from,i;
  st_node *a_node=root,*pre_node,*t_node;
  st_edge *t_edge;
  memset(root,0,sizeof(st_node));
  for(i=0;i<=len;i++){
    need_insert=0;
    pre_node=NULL;
    remainder++;
    if(i==len)
      need_insert=1;
    else if(a_len)
      if(str[a_node->edges[a_edge]->from+a_len]==str[i])
        if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
          a_node=a_node->edges[a_edge]->node;
          a_len=0;
        }
        else
          a_len++;
      else
        need_insert=1;
    else
      if(a_node->edges[str[i]-MIN_C])
        if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
          a_node=a_node->edges[str[i]-MIN_C]->node;
        else{
          a_edge=str[i]-MIN_C;
          a_len=1;
        }
      else
        need_insert=1;
    if(need_insert)
      for(;remainder>0;remainder--){
        if(!a_len)
          if(i==len){
            a_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
            a_node->edges[A_SIZE]->suffix_index=i-remainder+1;
            a_node->edges[A_SIZE]->node=NULL;
          }
          else{
            if(a_node->edges[str[i]-MIN_C]){
              if(pre_node)
                pre_node->suffix_link=a_node;
              if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
                a_node=a_node->edges[str[i]-MIN_C]->node;
              else{
                a_edge=str[i]-MIN_C;
                a_len=1;
              }
              break;
            }
            t_edge=(st_edge*)malloc(sizeof(st_edge));
            t_edge->from=i;
            t_edge->to=len-1;
            t_edge->suffix_index=i-remainder+1;
            t_edge->node=NULL;
            a_node->edges[str[i]-MIN_C]=t_edge;
            t_node=a_node;
          }
        else{
          if(i!=len && str[a_node->edges[a_edge]->from+a_len]==str[i]){
            if(pre_node)
              pre_node->suffix_link=a_node;
            if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
              a_node=a_node->edges[a_edge]->node;
              a_len=0;
            }
            else
              a_len++;
            break;
          }
          t_node=(st_node*)malloc(sizeof(st_node));
          memset(t_node,0,sizeof(st_node));
          t_edge=(st_edge*)malloc(sizeof(st_edge));
          t_edge->from=a_node->edges[a_edge]->from+a_len;
          t_edge->to=a_node->edges[a_edge]->to;
          t_edge->suffix_index=a_node->edges[a_edge]->suffix_index;
          t_edge->node=a_node->edges[a_edge]->node;
          from=a_node->edges[a_edge]->from;
          a_node->edges[a_edge]->node=t_node;
          a_node->edges[a_edge]->to=a_node->edges[a_edge]->from+a_len-1;
          t_node->edges[str[t_edge->from]-MIN_C]=t_edge;
          if(i==len){
            t_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
            t_node->edges[A_SIZE]->suffix_index=i-remainder+1;
            t_node->edges[A_SIZE]->node=NULL;
          }
          else{
            t_edge=(st_edge*)malloc(sizeof(st_edge));
            t_edge->from=i;
            t_edge->to=len-1;
            t_edge->suffix_index=i-remainder+1;
            t_edge->node=NULL;
            t_node->edges[str[i]-MIN_C]=t_edge;
          }
        }
        if(pre_node)
          pre_node->suffix_link=t_node;
        pre_node=t_node;
        if(a_node==root && a_len>0){
          if(remainder>1)
            a_edge=str[i-remainder+2]-MIN_C;
          from=i-remainder+2;
          a_len--;
        }
        else if(a_node!=root)
          if(a_node->suffix_link)
            a_node=a_node->suffix_link;
          else
            a_node=root;
        while(a_len>0 && a_len>=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1){
          a_len-=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
          from+=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
          a_node=a_node->edges[a_edge]->node;
          a_edge=str[from]-MIN_C;
        }
      }
  }
  return;
}
long long modPow(long long a,int x){
  long long res = 1;
  while(x>0){
    if(x%2)
      res=(res*a)%MOD;
    a=(a*a)%MOD;
    x>>=1;
  }
  return res;
}
void sort_a(int*a,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left,*right;
  left=(int*)malloc(m*sizeof(int));
  right=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++)
    left[i]=a[i];
  for(i=0;i<size-m;i++)
    right[i]=a[i+m];
  sort_a(left,m);
  sort_a(right,size-m);
  merge(a,left,right,m,size-m);
  free(left);
  free(right);
  return;
}
void merge(int*a,int*left,int*right,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[j];
            j++;
        } else if (j == right_size) {
            a[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            a[i+j] = left[i];
            i++;                
        } else {
            a[i+j] = right[j];
            j++;
        }
    }
    return;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll mod = 1e9+7;
const int nax = 1e5+10;
ll sum_pow[27][nax];

int main() {
  for (int i = 0; i <= 26; i++) {
    for (int j = 1; j < nax; j++) {
      ll v = 1;
      if (i) {
    v = (sum_pow[i-1][j]-sum_pow[i-1][j-1])*j;
      }
      sum_pow[i][j] = (sum_pow[i][j-1]+v) % mod;
    }
  }
  ios::sync_with_stdio(0); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = s.size();
    assert(n);
    vector<int> sa(n), rank(n), tmp(n);
    for (int i = 0; i < n; i++)
      sa[i] = i, rank[i] = s[i];
    for (int d = 1;; d *= 2) {
      auto cmp = [&](int i, int j) {
    auto a = make_pair(rank[i], i+d < n ? rank[i+d] : -1);
    auto b = make_pair(rank[j], j+d < n ? rank[j+d] : -1);
    return a < b;
      };
      sort(sa.begin(), sa.end(), cmp);
      int c = 0;
      for (int i = 0;; i++) {
    tmp[sa[i]] = c;
    if (i == n-1) break;
    c += cmp(sa[i],sa[i+1]);
      }
      swap(tmp,rank);
      if (c == n-1) break;
    }

    s += '@';
    vector<int> lcp(n,0);
    int k = 0;
    for (int i = 0; i < n; i++) {
      int j = rank[i];
      if (j == n-1) continue;
      while (s[sa[j]+k] == s[sa[j+1]+k]) k++;
      lcp[j+1] = k;
      if (k) k--;
    }

    /*for (int i = 0; i < n; i++) {
      cout << s.substr(sa[i]) << ' ' << lcp[i] << endl;
    }
    cout << endl;*/

    vector<vector<int>> next(n+1, vector<int>(26,n));
    for (int i = n-1; i >= 0; i--) {
      next[i] = next[i+1];
      next[i][s[i]-'a'] = i;
    }
    vector<vector<int>> count(n+1, vector<int>(26,0));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 26; j++) {
    count[i+1][j] = count[i][j]+(s[i] == 'a'+j);
      }
    }

    ll ans = 0;
    for (int i = 0; i < n; i++) {
      int l = lcp[i];
      int mask = 0;
      for (int j = 0; j < 26; j++)
    if (count[sa[i]+l][j]-count[sa[i]][j])
      mask |= 1<<j;
      int p = sa[i]+l;
      //cout << s.substr(sa[i]) << endl;
      //cout << s.substr(sa[i], l) << ": ";
      while (p < n) {
    int q = n;
    for (int j = 0; j < 26; j++) {
      if (!(mask>>j&1))
        q = min(q, next[p][j]);
    }
    //cout << s.substr(p,q-p) << '|';
    auto sum = sum_pow[__builtin_popcount(mask)];
    (ans += sum[q-sa[i]]-sum[p-sa[i]]) %= mod;
    if (q == n) break;
    int old_mask = mask;
    for (int j = 0; j < 26; j++)
      if (count[q+1][j]-count[sa[i]][j])
        mask |= 1<<j;
    assert(mask != old_mask);
    p = q;
      }
      //cout << endl;
      //for (int j = l+1; sa[i]+j <= s.size(); j++)
      //cout << s.substr(sa[i],j) << ' ';
      //cout << endl;
    }
    cout << (ans%mod+mod)%mod << endl;
  }
}

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'superFunctionalStrings' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */

    private static long[][] ar;
        public static void inIt()
        {
            ar = new long[100001][];
            long mod = 1000000007;
            ar[0] = new long[27];
            for (int i = 1; i < 100001; i++)
            {
                ar[i] = new long[27];
                ar[i][1] = i;
                for (int j = 2; j < 27; j++)
                {
                    ar[i][j] = ar[i][j - 1] * i % mod;
                }
            }
            for (int i = 1; i < 27; i++)
            {
                ar[0][i] = 0;
                long t = ar[1][i];
                for (int j = 2; j < 100001; j++)
                {
                    ar[j][i] = (t + ar[j][i]) % mod;
                    t = ar[j][i];
                }
            }
        }

        public static int superFunctionalStrings(string s)
        {
            int n = s.Length, a1,a2, lg=0;
            Dictionary<int, int>[] dc = new Dictionary<int, int>[n];
            dc[n - 1] = new Dictionary<int, int>();
            dc[n - 1].Add(s[n - 1] - 'a', n - 1);

            for (int i = n-2; i >= 0; i--)
            {
                dc[i] = new Dictionary<int, int>(dc[i + 1]);
                if (dc[i].ContainsKey(s[i] - 'a')) dc[i][s[i] - 'a'] = i;
                else dc[i].Add(s[i] - 'a', i);
            }
            Dictionary<ValueTuple<int, int, int>, int> d = new Dictionary<ValueTuple<int, int, int>, int>();
            long res = 0, mod = 1000000007;
            List<int> list = dc[0].Values.ToList();
            list.Sort();
            list.Add(n);
            res = countIt(list,lg);
            bool goOn = true;
            for (int i = 1; i < n; i++)
            {
                goOn = true;
               
                a1 = 0;
                a2 = i;
                lg = 0;
                
                while (goOn)
                {
                    goOn = false;
                    while (a2 < n && s[a1]==s[a2])
                    {
                        a1++;
                        a2++;
                        lg++;
                    }
                    if (a2<n)
                    {
                        if (d.ContainsKey((a1,lg,s[a2])))
                        {
                            a1 = d[(a1, lg, s[a2])];
                            goOn = true;
                        }
                        else
                        
                            d.Add((a1, lg, s[a2]), a2);
                        
                    }
                }
                if (a2 < n)
                {
                    list = dc[i].Values.ToList();
                    list.Sort();
                    list.Add(n);
                    res = (res + countIt(list, lg)) % mod;
                }
                    
            }
            return (int)res;
        }

        private static int countIt(List<int> list, int lg)
        {

            long res = 0, mod = 1000000007;
            int n = list.Count, str= list[0], m;
            for (int i = 1; i < n; i++)
            {
                m = list[i] - str;
                if (m - lg <1) continue;
                res = (res + ar[m][i] - ar[lg][i])%mod;
                if (res < 0) res += mod;
                lg = m;
            }
            
            return (int)res;
        }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int t = Convert.ToInt32(Console.ReadLine().Trim());
        Result.inIt();
        for (int tItr = 0; tItr < t; tItr++)
        {
            string s = Console.ReadLine();

            int result = Result.superFunctionalStrings(s);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

import java.io.*;
import java.util.*;

public class Solution {

  static final int MOD = 1_000_000_007;
  static final int MAX = 100000;

  static class Suffix {
    int index;
    int[] rank = new int[2];
  }

  static Comparator<Suffix> cmp =
      (a, b) -> {
        return (a.rank[0] == b.rank[0]) ? a.rank[1] - b.rank[1] : a.rank[0] - b.rank[0];
      };
  
  static int[] invSuff = new int[MAX];
  static int[] suffixArr = new int[MAX];
  static int[] lcp = new int[MAX];
  
  static void buildSuffixArray(char[] txt) {
    int n = txt.length;
    Suffix[] suffixes = new Suffix[n];

    for (int i = 0; i < n; i++) {
      suffixes[i] = new Suffix();
      suffixes[i].index = i;
      suffixes[i].rank[0] = txt[i] - 'a';
      suffixes[i].rank[1] = ((i + 1) < n) ? (txt[i + 1] - 'a') : -1;
    }

    Arrays.sort(suffixes, cmp);

    int[] ind = new int[n];

    for (int k = 4; k < 2 * n; k = k * 2) {
      int rank = 0;
      int prev_rank = suffixes[0].rank[0];
      suffixes[0].rank[0] = rank;
      ind[suffixes[0].index] = 0;

      for (int i = 1; i < n; i++) {
        if (suffixes[i].rank[0] == prev_rank && suffixes[i].rank[1] == suffixes[i - 1].rank[1]) {
          prev_rank = suffixes[i].rank[0];
          suffixes[i].rank[0] = rank;
        } else {
          prev_rank = suffixes[i].rank[0];
          suffixes[i].rank[0] = ++rank;
        }
        ind[suffixes[i].index] = i;
      }

      for (int i = 0; i < n; i++) {
        int nextindex = suffixes[i].index + k / 2;
        suffixes[i].rank[1] = (nextindex < n) ? suffixes[ind[nextindex]].rank[0] : -1;
      }

      Arrays.sort(suffixes, cmp);
    }

    for (int i = 0; i < n; i++) {
      suffixArr[i] = suffixes[i].index;
      invSuff[suffixArr[i]] = i;
    }
  }

  static void kasai(char[] txt) {
    int n = txt.length;
    int k = 0;

    for (int i = 0; i < n; i++) {
      if (invSuff[i] == n - 1) {
        k = 0;
        continue;
      }
      int j = suffixArr[invSuff[i] + 1];
      while (i + k < n && j + k < n && txt[i + k] == txt[j + k]) {
        k++;
      }

      lcp[invSuff[i]] = k;

      if (k > 0) {
        k--;
      }
    }
  }
  
  static long superFunctionalStrings(char[] s, int[][] map) {
    buildSuffixArray(s);
    kasai(s);

    int len = s.length;

    @SuppressWarnings("unchecked")
    Map<Integer, Integer>[] letterPlaceArr = new Map[len];
    letterPlaceArr[len - 1] = new HashMap<>();
    letterPlaceArr[len - 1].put((s[len - 1]) - 'a', len - 1);
    for (int i = len - 2; i >= 0; i--) {
      letterPlaceArr[i] = new HashMap<>(letterPlaceArr[i + 1]);
      letterPlaceArr[i].put(s[i] - 'a', i);
    }

    long result = 0;
    for (int i = 0; i < len; i++) {
      int nowLen = i == 0 ? 0 : lcp[i - 1];

      int startIndex = suffixArr[i];
      
      List<Integer> tempArr = new ArrayList<Integer>(letterPlaceArr[startIndex].values());
      tempArr.add(len);
      Collections.sort(tempArr);

      for (int j = 1, tempLen = tempArr.size(); j < tempLen; j++) {
        if (tempArr.get(j) - startIndex <= nowLen) {
          continue;
        }

        int diff =
            map[tempArr.get(j) - startIndex][j] - map[Math.max(tempArr.get(j-1) - startIndex, nowLen)][j];
        if (diff < 0) {
          diff += MOD;
        }
        result = (result + diff) % MOD;
      }
    }

    return result;
  }

  static int[][] init() {
    int[][] map = new int[100001][28];
    for (int i = 1; i <= 100000; i++) {
      long temp = 1;
      for (int j = 1; j <= 26; j++) {
        temp = (temp * i) % MOD;
        map[i][j] = (int)temp;
      }
    }

    for (int j = 1; j <= 26; j++) {
      map[0][j] = 0;
      int temp = map[1][j];
      for (int i = 2; i <= 100000; i++) {
        map[i][j] = (temp + map[i][j]) % MOD;
        temp = map[i][j];
      }
    }

    return map;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int t = Integer.parseInt(st.nextToken());

    int[][] map = init();

    for (int i = 0; i < t; i++) {
      char[] s = br.readLine().toCharArray();
      long result = superFunctionalStrings(s, map);

      bw.write(String.valueOf(result));
      bw.newLine();
    }
    
    bw.close();
    br.close();
  }
}

'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++];
}

/*
 * Complete the superFunctionalStrings function below.
 */
function superFunctionalStrings(s) {

    var i, j;
    var str_list = [];
    var s_str = "";
    for (i = 0; i < s.length; i++) {
        for (j = i + 1; j < s.length + 1; j++) {
            s_str = s.substring(i, j);
            if (str_list.indexOf(s_str) == -1) {
                str_list.push(s_str);
            }
        }
    }
    var chr_list;
    var sum = 0;
    console.log("---------------------------------");
    for (i = 0; i < str_list.length; i++) {
        chr_list = [];
        if (str_list[i] == "") {
            continue;
        }
        for (j = 0; j < str_list[i].length; j++) {
            if (str_list[i][j] == '') {
                continue;
            }
            if (chr_list.indexOf(str_list[i][j]) == -1) {
                chr_list.push(str_list[i][j]);
            }
        }
        console.log(str_list[i] + "  " + (findPow(str_list[i].length, chr_list.length)));
        console.log(str_list[i].length + " " + chr_list.length);
        sum = (sum + (findPow(str_list[i].length, chr_list.length))) % (Math.pow(10, 9) + 7)
    }

    return sum;
}
function findPow(a, b) {
    var i;
    var result = 1;
    for (i = 0; i < b; i++) {
        result = (result * a) % (Math.pow(10, 9) + 7)
    }
    return result;
}
function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

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

    for (let tItr = 0; tItr < t; tItr++) {
        const s = readLine();

        let result = superFunctionalStrings(s);

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

    ws.end();
}

from string import ascii_lowercase
from bisect import bisect_left, bisect_right
from itertools import zip_longest, islice

MOD = 7 + 10 ** 9

N = 10 ** 5

sum_pow = [[0] * (N + 1) for k in range(27)]
for k in range(1, 27):
    for n in range(1, N + 1):
        sum_pow[k][n] = (sum_pow[k][n - 1] + pow(n, k, MOD)) % MOD
        
        
def get_sp(left, right, k):
    if left > right or right <= 0:
        return 0
    if left <= 0:
        return sum_pow[k][right]
    return (sum_pow[k][right] + MOD - sum_pow[k][left - 1]) % MOD


def all_occ(s):
    n = len(s)
    occ = [[] for _ in range(26)]
    for i in range(n):
        occ[ord(s[i]) - ord('a')].append(i)
    return occ

def occ_from_i(occ, i):
    occ_i = []
    for j in range(26):
        if len(occ[j]) == 0 or i > occ[j][-1]:
            continue
        first = bisect_left(occ[j], i)
        occ_i.append(occ[j][first])
    return sorted(occ_i)


def sorted_idx(items):
    unique = sorted(set(items))
    idx = dict(zip(unique, range(len(unique))))
    return [idx[v] for v in items]

def suffix_array(s):
    n = len(s)
    k = 1
    sa = sorted_idx(s)
    while max(sa) < n - 1:
        sa = sorted_idx([a * (n + 1) + b + 1 for
                         (a, b) in zip_longest(sa,
                                               islice(sa, k, None),
                                               fillvalue=-1)])
        k <<= 1
    return sa

def lcp_sa(s):
    inv_sa = suffix_array(s)
    n = len(inv_sa)
    sa = [0] * n
    for i in range(n):
        sa[inv_sa[i]] = i
    lcp = [0] * n
    k = 0
    for i in range(n):
        if inv_sa[i] == n - 1:
            k = 0
            continue
        j = sa[inv_sa[i]+1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[inv_sa[i] + 1] = k
        if k > 0:
            k -= 1
    return sa, lcp

def solve(s):
    n = len(s)
    occ = all_occ(s)
    sa, lcp = lcp_sa(s)
    ans = 0
    #print(sa)
    #print(lcp)
    for i in range(n):
        o = occ_from_i(occ, sa[i])
        t = sa[i] + lcp[i]
        if t >= o[-1]:
            ans = (ans + get_sp(lcp[i] + 1, n - sa[i], len(o))) % MOD
            continue
        k = bisect_right(o, t)
        ans = (ans + get_sp(lcp[i] + 1, o[k] - sa[i], k)) % MOD
        for j in range(k + 1, len(o)):
            ans = (ans + get_sp(o[j - 1] - sa[i] + 1, o[j] - sa[i], j)) % MOD
        
        ans = (ans + get_sp(o[-1] - sa[i] + 1, n - sa[i], len(o))) % MOD
        
    return ans

def sum_p_bf(left, right, k):
    ans = 0
    for n in range(max(left, 1), right + 1):
        ans = (ans + pow(n, k, MOD)) % MOD
    return ans

q = int(input().strip())
for _ in range(q):
    string = input().strip()
    print(solve(string))