output_description: Print the answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: import sys
  
  readline = sys.stdin.readline
  
  
  def SAIS(Sorgin):
      # O(N+sigma)
      # 非負数列を入れる
      S = Sorgin + [-1]
      ls = len(S)
      lstable = [1] * ls
      # 0ならL-type, 1ならLMSではないS-type, LMSについては何番目に大きいLMSかを格納
      LMS = []
      bucst = [1] + [0] * ls
      cnt = -1
      for i in range(ls - 2, -1, -1):
          bucst[S[i] + 1] += 1
          if S[i] > S[i + 1] or (S[i] == S[i + 1] and not lstable[i + 1]):
              lstable[i] = 0
              if lstable[i + 1]:
                  lstable[i + 1] = cnt
                  cnt -= 1
                  LMS.append(i + 1)
  
      LMS.reverse()
  
      for i in range(ls):
          bucst[i] += bucst[i - 1]
      bucen = [bucst[i + 1] - 1 for i in range(ls)] + [0]
  
      bucst2 = bucst[:]
      bucen2 = bucen[:]
      bucen3 = bucen[:]
      bucen4 = bucen[:]
      table = [None] * ls
      for idx in LMS:
          table[bucen[S[idx]]] = idx
          bucen[S[idx]] -= 1
      for i in range(ls):
          if not table[i]:
              continue
          # <=> if table[i] == 0 or table[i] is None
          k = table[i] - 1
          if not lstable[k]:
              table[bucst[S[k]]] = k
              bucst[S[k]] += 1
      for i in range(ls - 1, -1, -1):
          if not table[i]:
              continue
          k = table[i] - 1
          if lstable[k]:
              table[bucen2[S[k]]] = k
              bucen2[S[k]] -= 1
  
      table[0] = ls - 1
      lmsnum = len(LMS)
      lmssubord = [None] * lmsnum
      lmssubord[0] = ls - 1
      lmssublen = [l2 - l1 + 1 for l1, l2 in zip(LMS, LMS[1:])] + [1]
      cnt = 1
      repet = False
      for t in table[1:]:
          if lstable[t] < 0:
              lmssubord[cnt] = t
              cntlen = lmssublen[lstable[t]]
              if (
                  cntlen == lmssublen[lstable[lmssubord[cnt - 1]]]
                  and S[t : t + cntlen]
                  == S[lmssubord[cnt - 1] : lmssubord[cnt - 1] + cntlen]
              ):
                  repet = True
                  lstable[t] = lstable[lmssubord[cnt - 1]]
                  # ここでlstableはLMSsubstringについて同じものをまとめたものを格納するようになっている
                  cnt += 1
                  continue
              cnt += 1
      if repet:
          lmssubinv = [None] * ls
          for i in range(lmsnum):
              lmssubinv[lmssubord[i]] = i
          sublst = [lmssubinv[LMS[lstable[t]]] for t in LMS]
          lmssubord = [LMS[r] for r in SAIS(sublst)]
  
      table = [None] * ls
      for idx in lmssubord[::-1]:
          table[bucen3[S[idx]]] = idx
          bucen3[S[idx]] -= 1
      for i in range(ls):
          if not table[i]:
              continue
          # <=> if table[i] == 0 or table[i] is None
          k = table[i] - 1
          if not lstable[k]:
              table[bucst2[S[k]]] = k
              bucst2[S[k]] += 1
      for i in range(ls - 1, -1, -1):
          if not table[i]:
              continue
          k = table[i] - 1
          if lstable[k]:
              table[bucen4[S[k]]] = k
              bucen4[S[k]] -= 1
      return table[1:]
  
  
  def salcp(S, SAorg):
      N = len(S)
      lcp = [0] * N
      SA = SAorg + [N]
      SAinv = [None] * N
      for i in range(N):
          SAinv[SA[i]] = i
      h = 0
      for i in range(N):
          j = SA[SAinv[i] + 1]
          if h:
              h -= 1
          while i + h < N and j + h < N and S[i + h] == S[j + h]:
              h += 1
          lcp[SAinv[i]] = h
      return lcp
  
  
  S = list(map(lambda x: ord(x) - 97, readline().strip()))
  N = len(S)
  
  table = [0] * 26
  for s in S:
      table[s] = 1
  
  table[0] -= 1
  for i in range(1, 26):
      table[i] += table[i - 1]
  
  S = [table[s] for s in S]
  
  SA = SAIS(S)
  LCP = salcp(S, SA)
  
  leng = [N - sa for sa in SA]
  
  ans = sum(l * (l + 1) // 2 for l in leng) - sum(c * (c + 1) // 2 for c in LCP)
  print(ans)
  
problem_description: Statement
  
  You are given a string of length N. Calculate the number of distinct
  substrings of S.
samples: [{"input": "abcbcba", "output": "21\n    \n\n* * *"}, {"input": "mississippi", "output": "53\n    \n\n* * *"}, {"input": "ababacaca", "output": "33\n    \n\n* * *"}, {"input": "aaaaa", "output": "5"}]