Problem:
 Score : 500 points    Problem Statement You have a string A = A_1 A_2 ... A_n consisting of lowercase English letters.  You can choose any two indices i and j such that 1 \leq i \leq j \leq n and reverse substring A_i A_{i+1} ... A_j .  You can perform this operation at most once.  How many different strings can you obtain?      Constraints  1 \leq |A| \leq 200,000  A consists of lowercase English letters.         Input Input is given from Standard Input in the following format:  A       Output Print the number of different strings you can obtain by reversing any substring in A at most once.        Sample Input 1 aatt      Sample Output 1 5  You can obtain aatt (don't do anything), atat (reverse A[2..3] ), atta (reverse A[2..4] ), ttaa (reverse A[1..4] ) and taat (reverse A[1..3] ).       Sample Input 2 xxxxxxxxxx      Sample Output 2 1  Whatever substring you reverse, you'll always get xxxxxxxxxx .       Sample Input 3 abracadabra      Sample Output 3 44

Solution (Python):
A=input()
n=len(A)
from collections import defaultdict
d = defaultdict(int)
for i in A:
    d[i]+=1
a=0
for i in d.values():
    a+=i*(i-1)//2
print(n*(n-1)//2+1-a)

Solution (Python):
A=input()
n=len(A)
from collections import defaultdict
d = defaultdict(int)
for i in A:
    d[i]+=1
a=0
for i in d.values():
    a+=i*(i-1)//2
print(n*(n-1)//2+1-a)

Solution (Python):
A = list(input())
N = len(A)

ans = N * (N - 1) // 2 + 1

R = {}
for a in A:
  if a not in R: R[a] = 1
  else: R[a] += 1

for n in R.values():
  ans -= n * (n - 1) // 2

print(ans)

Solution (Python):
from collections import Counter
A=list(input())
m=len(A)

B=Counter(A)

cnt=0
for i in A:
    B[i] -=1
    cnt +=B[i]
print(m*(m-1)//2-cnt+1)

Solution (Python):
from collections import Counter
A=list(input())
length=len(A)

B=Counter(A)

cnt=0
for i in A:
    B[i] -=1
    cnt +=B[i]
print(length*(length-1)//2-cnt+1)

Solution (Python):
s = input()

dist = -1
for i in range(26):
    temp = s.count(chr(ord("a")+i))
    dist += temp * ~-temp // 2

print(len(s) * ~-len(s) // 2 - dist)

Solution (Python):
from collections import defaultdict as dd
A = input()
N = len(A)
d = dd(int)
for i in range(N):
	d[A[i]] += 1
cnt = 0
for v in d.values():
	cnt += v*(v-1)//2
print(N*(N-1)//2 - cnt + 1)

Solution (Python):
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)


input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve(n=None, s1=None, s2=None):
    s = getS()
    cnt = Counter(s)
    n = len(s)
    ans = 0
    for k, v in cnt.items():
        ans += v * (n - v)
        

    ans //= 2
    ans += 1

    print(ans)


def main():
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    
    solve()

Solution (Python):
from collections import Counter
s = input()
n = len(s)
print(n * ~-n // 2 + 1 - sum(i * ~-i // 2 for i in Counter(s).values()))

Solution (Python):
a=input()
ans=1
from collections import defaultdict
d = defaultdict(int)
for i in range(len(a)):
    d[a[i]]+=1
    ans+=(i+1-d[a[i]])
print(ans)

Solution (Python):
from collections import Counter
a=input()
cnt=Counter(a)
n=len(a)
ans=n*(n-1)//2+1

for v in cnt.values():
    ans-=v*(v-1)//2

print(ans)

Solution (Python):
A = input().strip()
N = len(A)
tot = 1+(N*(N-1))//2
C = {chr(i):[] for i in range(97,123)}
for i in range(N):
    C[A[i]].append(i)
cnt = 0
for a in C:
    n = len(C[a])
    cnt += (n*(n-1))//2
print(tot-cnt)

Solution (Python):
import sys
from collections import Counter
 
A = sys.stdin.readline().strip()
la = len(A)
 
ans = la * (la - 1) // 2 + 1
counter = Counter(A)
for key, count in counter.items():
    if count == 1:
        continue
    ans -= count * (count - 1) // 2
 
print(ans)

Solution (Python):
import sys
def LS2(): return list(sys.stdin.readline().rstrip())  


A = LS2()
N = len(A)



from collections import defaultdict

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1

ans = 0
for key in d.keys():
    ans += d[key]*(N-d[key])

ans //= 2
ans += 1
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


A = LS2()
N = len(A)

from collections import defaultdict

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1


ans = 0
for key in d.keys():
    ans += d[key]*(N-d[key])

ans //= 2
ans += 1
print(ans)

Solution (Python):
from collections import Counter


A = input()
N = len(A)
cntr = Counter(A)
ans = 0
for c in A:
    ans += N - cntr[c]
ans //= 2
print(ans + 1)

Solution (Python):
s=input()
l={}
for i in s:
  if i in l:
    l[i]+=1
  else:
    l[i]=1

def c(x):
  return x*(x-1)//2

sm=c(len(s))
for i in l:
  sm-=c(l[i])
print(sm+1)

Solution (Python):
a = input()
count = [0]*26
ans = 1
for i in range(len(a)):
    x = ord(a[i])-ord("a")
    ans += i-count[x]
    count[x] += 1
print(ans)

Solution (Python):
a = input()
n = len(a)

l = [0]*(2*n-1)
i = 0
j = 0
while i < 2*n - 1:
    while i >= j and i+j+1 < 2*n and a[(i-j)//2] == a[(i+j+1)//2]:
        j += 1
    l[i] = j
    k = 1
    while i + k < 2*n-1 and i >= k and l[i] >= k and l[i-k] != l[i]-k:
        l[i+k] = min(l[i-k],l[i]-k)
        k += 1
    i += k
    if j > k:
        j -= k
    else:
        j = 0
ans = n*(n-1)//2+1
count = [0]*26
for i in a:
    count[ord(i)-ord("a")] += 1
for i in count:
    ans -= i*(i-1)//2
print(ans)

Solution (Python):
from collections import Counter

a = input()
cnta = Counter(a)

ans = (len(a)** 2 - len(a)) // 2 + 1
for i in cnta.values():
    ans -= (i ** 2 - i) // 2
print(ans)

Solution (Python):



A=input()

A=list(map(lambda x:ord(x)-97,A))

log=[0]*26
log[A[0]]+=1
ans=1


for i in range(1,len(A)):
    ans+=i-log[A[i]]
    log[A[i]]+=1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

A = input()[:-1]
cnt = defaultdict(int)
ans = 0

for i in range(len(A)):
    ans += i-cnt[A[i]]
    cnt[A[i]] += 1

print(ans+1)

Solution (Python):
import collections
S=list(input())
a=len(S)
ans=(a*(a-1))//2
ans+=1
c = collections.Counter(S)
for b in c.values():
  ans-=(b*(b-1))//2
print(ans)

Solution (Python):
d=dict(zip([chr(i+97) for i in range(26)],[0]*26))
a=input()
n=len(a)
for i in a:
  d[i]+=1
ans=n*(n-1)//2+1
for i in d.values():
  ans-=i*(i-1)//2
print(ans)

Solution (Python):
from collections import Counter
a = input()
n = len(a)

cnt = Counter(a)
ans = n * (n - 1) // 2 - sum(m * (m - 1) // 2 for m in cnt.values()) + 1
print(ans)

Solution (Python):
from collections import Counter
s = str(input())
n = len(s)
ans = 1 + n * (n-1) // 2
for k, v in Counter([x for x in s]).items():
    ans -= v * (v-1) // 2
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    s = input()
    l = len(s)
    counter = Counter()
    ans = 1

    for i in range(l):
        char = s[i]
        ans += i - counter[char]
        counter[char] += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A = input()
N = len(A)

ans = N*(N-1)//2

for v in Counter(A).values():
	ans -= v*(v-1)//2

print(ans+1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



A = input()

n = len(A)
ans = n*(n+1)//2 + 1

for v in Counter(A).values():
	ans -= v*(v+1)//2

print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7

    s=SI()
    n=len(s)
    dict_=defaultdict(lambda:0)
    for i in range(n):
        dict_[s[i]]+=1
    ans=1+(n*(n-1))//2
    for x in dict_.keys():
        ans-=(dict_[x]*(dict_[x]-1))//2
    print(ans)
        
            
            
            
            
        
    
    
    
    



if __name__=="__main__":
    main()

Solution (Python):
import sys
from string import ascii_lowercase as a2z

input = sys.stdin.readline


def main():
    A = input().rstrip()

    count = {al: 0 for al in a2z}
    ans = 1
    for i, a in enumerate(A):
        ans += (i - count[a])
        count[a] += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
A = input()
n = len(A)-1
ans = int(n*(n+1) // 2) + 1
count_a = Counter(A)
for c in count_a.values():
    ans -= ((c * (c-1)) // 2)
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





A = input()
Ac = Counter(A)
cnt = 0




















for val in Ac.values():
    cnt += val * (val - 1) // 2
print(len(A) * (len(A)-1) // 2 - cnt + 1)

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    s = input()
    c = collections.Counter(s)

    l = len(s)
    total = l * (l - 1) // 2

    for ci in c.values():
        tmp = ci * (ci - 1) // 2
        total -= tmp

    print(total + 1)


if __name__ == '__main__':
    main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





A = input()
Ac = Counter(A)
cnt = 0
for val in Ac.values():
    cnt += val * (val - 1) // 2
print(len(A) * (len(A)-1) // 2 - cnt + 1)

Solution (Python):
a=list(input())

unko=[0]*(ord("z")+1-ord("a"))

for aa in a:
    unko[ord(aa)-ord("a")]+=1
tmp=0
for u in unko:
    tmp+=(u*(u-1))//2

print((len(a)*(len(a)-1))//2-tmp+1)

Solution (Python):
print(2+len(a:=input())**2-sum(a.count(x)**2for x in set(a))>>1)

Solution (Python):
print((len(a:=input())**2-sum(a.count(x)**2for x in set(a)))//2+1)

Solution (Python):
print((len(a:=input())**2-sum(map(lambda x:x*x,map(a.count,[chr(i)for i in range(97,123)]))))//2+1)

Solution (Python):
import collections
A= input()
Ac = collections.Counter(A)
cnt = 0
for val in Ac.values():
    cnt += val*(val-1)//2
print(len(A)*(len(A)-1)//2-cnt+1)

Solution (Python):
s = input().rstrip()
n = len(s)
ans = n * (n-1) // 2

from string import ascii_lowercase

for c in ascii_lowercase:
    m = s.count(c)
    ans -= m * (m-1) // 2

print(ans + 1)

Solution (Python):
from collections import defaultdict


def main():
    a = input()
    cnt = defaultdict(lambda: 0)
    for aa in a:
        cnt[aa] += 1
    ans = len(a) * (len(a) - 1) // 2 + 1
    for c, n in cnt.items():
        ans -= n * (n - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    a = input()
    n = len(a)
    total = (n - 1) * n // 2 + 1

    D = Counter(a)
    for v in D.values():
        total -= (v - 1) * v // 2
    print(total)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import Counter


def main():
    A = input()
    N = len(A)
    c = Counter(A)
    print(1 + N * (N - 1) // 2 - sum([v * (v - 1) // 2 for v in c.values()]))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
A = input()
n = len(A)
c = Counter(A)

ans = 1
ans += n*(n-1)//2
for v in c.values():
    ans -= v*(v-1)//2
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

A = readline().rstrip()

def nC2(x):
  return (x * (x - 1)) // 2

from collections import defaultdict
dic = defaultdict(int)

for a in A:
  dic[a] += 1
  
ans = nC2(len(A))
for v in dic.values():
  ans -= nC2(v)

print(ans + 1)

Solution (Python):
A = input()

dp = [0]*len(A)
dp[0] = 1
dic = {chr(ord('a')+i):0 for i in range(26)}
dic[A[0]] += 1

for i in range(1,len(A)):
  dp[i] = dp[i-1] + i - dic[A[i]]
  dic[A[i]] += 1
  
print(dp[-1])

Solution (Python):

















s = list(input())
d = {}
for c in s:
    if c not in d:
        d[c] = 1
    else:
        d[c] += 1
ans = len(s) * (len(s) - 1) // 2 + 1
for v in d.values():
    ans -= v * (v - 1) // 2
print(ans)

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    A = input()
    N = len(A)
    l = Counter(A)
    ans = N*(N+1)//2 + 1 - N
    for x in l.values():
        ans -= x*(x-1)//2
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
dic = defaultdict(int)
S = str(input())
N = len(S)
for i in range(N):
  dic[S[i]] += 1


ans = 1 
L = list(dic.keys())
for i in range(len(L)):
  for j in range(i+1,len(L)):
    temp = dic[L[i]]*dic[L[j]]
    ans += temp
print(ans)

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    S = list(in_s())
    N = len(S)
    cnt = Counter(S)

    ans = N * (N - 1) // 2 + 1

    orda = ord('a')
    for c in range(orda, orda + 26):
        c = chr(c)
        n = cnt[c]
        ans -= n * (n - 1) // 2

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter

A = sys.stdin.readline().strip()
la = len(A)

ans = la * (la - 1) // 2 + 1
counter = Counter(A)
for key, count in counter.items():
    if count == 1:
        continue
    ans -= count * (count - 1) // 2

print(ans)

Solution (Python):



from collections import Counter
def main():
    A = input()
    n = len(A)
    A = Counter(A)
    ret = n *(n-1)//2
    for i, c in A.items():
        ret -= c*(c-1)//2
    print(ret+1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

def main():
    A = list(input())
    d = defaultdict(int)
    for a in A:
        d[a] += 1
    ans = 1
    for i in range(97,123):
        for j in range(i+1,123):
            ans += d[chr(i)] * d[chr(j)]

    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    A = input()
    n = len(A)

    res = (n - 1) * n // 2 + 1
    D = Counter(A)
    for v in D.values():
        if v >= 2:
            res -= (v - 1) * v // 2
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




S = S()
N = len(S)

dic = DD(int)
for s in S:
  dic[s] += 1

ans = N*(N-1)//2
for k in dic:
  t = dic[k]
  ans -= t*(t-1)//2

print(ans+1)

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

A = input().rstrip()
d = defaultdict(int)
for i in range(len(A)):
    d[A[i]] += 1
    
s = 0
for k in d.keys():
    s += d[k]

ans = 0
for k in d.keys():
    s -= d[k]
    ans += d[k]*s
print(ans+1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


a = input()
n = len(a)
from collections import defaultdict
d = defaultdict(int)
s = 0
ans = 0
for i,c in enumerate(a):
    ans += (s - d[c])
    d[c] += 1
    s += 1
print(ans+1)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


S = input()
L = len(S)
mp = {}
for c in [chr(i) for i in range(97, 97+26)]:
    mp[c] = 0


for i in range(L):
    mp[S[i]] += 1

res = 0
for i in range(L):
    res += L - mp[S[i]]

res //= 2

print(res+1)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



S = input()
count = [0] * 26
for c in S:
    count[ord(c) - ord('a')] += 1

n = len(S)
ans = n * (n - 1) // 2 + 1
for c in count:
    ans -= c * (c - 1) // 2
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

s = S()
D = defaultdict(int)
for i in s:
    D[i]+=1

ans = len(s) * (len(s) - 1) // 2
for j in D.values():
    ans -= j * (j - 1) // 2

print(ans + 1)

Solution (Python):
a=input()
n=len(a)
from collections import Counter
ca=Counter(a)
ans=(n*(n-1))//2+1
for v in ca.values():
  ans-=(v*(v-1))//2
print(ans)

Solution (Python):
from collections import Counter, deque, OrderedDict, defaultdict




from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product









import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    A=list(input())
    AA=Counter(A)

    ans=1
    alpha=list(chr(ord('a')+i) for i in range(26))
    
    for i, j in product(alpha,repeat=2):
        if i<j:
            ans+=AA[i]*AA[j]


    print(ans)


    
resolve()

Solution (Python):
n=input()
m=len(n)

A={chr(i):0 for i in range(97,97+26)}
B={chr(i):0 for i in range(97,97+26)}

cnt=0
for i in range(m):
    A[n[i]] +=1
for i in range(m):
    B[n[i]] +=1
    cnt +=A[n[i]]-B[n[i]]
print(m*(m-1)//2-cnt+1)

Solution (Python):
from collections import defaultdict

a = input()
len_a = len(a)
ans = 1 + len_a*(len_a-1)//2

d = defaultdict(int)
for ai in a:
    d[ai] += 1

for key,val in d.items():
    ans -= val*(val-1)//2

print(ans)

Solution (Python):
import collections
a=input()
c=collections.Counter(a)
l=len(a)
s=-1
for i in c.values():s+=i*(i-1)//2
print(l*(l-1)//2-s)

Solution (Python):
import collections
a = list(input())
c = collections.Counter(a)
n = len(a)
ans = n*(n-1)//2 + 1
for v in c.values():
    ans -= v*(v-1)//2
print(ans)

Solution (Python):
A=list(input())
n=len(A)
ind=[[] for i in range(26)]
for i in range(n):
    ind[ord(A[i])-97].append(i)
cnt=0
for i in range(26):
    cnt+=len(ind[i])*(len(ind[i])-1)//2

print(n*(n-1)//2-cnt+1)

Solution (Python):
A = input()

Alphabet = list("abcdefghijklmnopqrstuvwxyz")

N = len(A)
ans = N*(N-1)/2 + 1

for i in Alphabet:
  z = 0
  for j in range(len(A)):
    if i == A[j]:
      z+=1
  if z>1:
    ans -= z*(z-1)/2
    
print(int(ans))

Solution (Python):
from collections import Counter
a = input()
n = len(a)
c = Counter(a)

tp = 0
for val in c.values():
    tp += (val*(val-1))//2

print((n*(n-1)//2)-tp+1)

Solution (Python):
s = input()
n = len(s)

from collections import Counter
cnt = Counter(s)

ans = n * (n - 1) // 2 + 1
for _, x in cnt.items():
    ans -= x * (x - 1) // 2

print(ans)

Solution (Python):
from collections import Counter

a = input()
n = len(a)
ans = 1 + n * (n-1) // 2
b = Counter(a)

c = list(b.values())
for i in c:
    ans -= (i-1) * i // 2
    
print(ans)

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

counter = Counter(read().rstrip()).values()

counter

N = sum(counter)
x = N * (N - 1) // 2 + 1
x -= sum(x * (x - 1) // 2 for x in counter)
print(x)

Solution (Python):
from collections import Counter
A=input()

N=len(A)
C=Counter(A)
ans=N*(N-1)//2
for v in C.values():
    ans-=(v*(v-1)//2)

print(1+ans)

Solution (Python):
from collections import Counter

A = input()

c = Counter(A)
N = len(A)
ans = N * (N - 1) // 2 + 1
for i in c.values():
    ans -= i * (i - 1) // 2
print(ans)

Solution (Python):
from collections import deque
alphabet = "abcdefghijklmnopqrstuvwxyz"
A = input()
d = {a:deque() for a in "abcdefghijklmnopqrstuvwxyz"}
i = 0
while i < len(A):
  d[A[i]].append(i)
  i += 1
ans = 1+len(A)*(len(A)-1)//2
i = 0
while i < 26:
  a = alphabet[i]
  ans -= len(d[a])*(len(d[a])-1)//2
  i += 1
print(ans)

Solution (Python):
from collections import Counter

S = input()
c = Counter(S)
N = len(S)
ans = 1

for i in range(N-1):
    s = S[i]
    ans += N-c[s]
    c[s] -= 1
    N -= 1

print(ans)

Solution (Python):

"""
全通りのスワップから、重複する要素を引くことで求まる。
(解説では、この逆で貪欲に重複しない要素を数え上げる解法だが、本質的には同じ)

1.Ai==Ajとなる添字を選んだとき、その結果は
A[i+1:j]の結果と等しくなるのでこれを省く。

2.Ai!=Ajとなる添字を選んだとき、必ずそれと重複するようなスワップの方法、また
スワップをしなかった場合とは異なるものになる。

よって、答えは全通りからi<jとなるAi,Ajに対して、Ai==Ajの個数を引いた数になる。
つまり、文字列の長さをnとしたとき、まず全通りは
ans = nC2
で表され、
ここからi<jとなるi,jにおいて、Ai==Ajとなる文だけ引く。
このとき、Kという事前に準備した配列を用いているが、
各アルファベットの出現回数について、一括で重複回数を求められるようにしてある。
"""
import sys
from collections import defaultdict
dic1 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
s = readline().rstrip().decode('utf-8')
n = len(s)


def large_conbination(n,k): 
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
    res2 = 1
    for i in range(1,k+1):
        res2*= i
    return res1//res2

ans = large_conbination(n,2)

for i in s:
    dic1[i] += 1

K = [0]
for i in range(2*(10**5)):
    K.append(K[-1]+(i+1))

for i in dic1.values():
    if i < 2:
        continue
    ans -= K[i-1]

print(ans+1)

Solution (Python):
import collections
A = input()
C = collections.Counter(A)
ans = len(A)*(len(A)-1)//2
for v in C.values():
    ans -= v*(v-1)//2
print(ans+1)

Solution (Python):
a = input()
n = len(a)
cnt = [0]*(ord('z')-ord('a')+1)


res = 0
for s in a:
    idx = ord(s) - ord('a')
    res += cnt[idx]
    cnt[idx]+= 1
ans = (n*(n-1)/2)-res+1
print(int(ans))