Problem:


Score : 200 points

Problem Statement

You are given a string S of length N.
Among its subsequences, count the ones such that all characters are different, modulo 10^9+7. Two subsequences are considered different if their characters come from different positions in the string, even if they are the same as strings.

Here, a subsequence of a string is a concatenation of one or more characters from the string without changing the order.

Constraints

1 \leq N \leq 100000

S consists of lowercase English letters.

|S|=N

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of the subsequences such that all characters are different, modulo 10^9+7.

Sample Input 1

4
abcd

Sample Output 1

15

Since all characters in S itself are different, all its subsequences satisfy the condition.

Sample Input 2

3
baa

Sample Output 2

5

The answer is five: b, two occurrences of a, two occurrences of ba. Note that we do not count baa, since it contains two as.

Sample Input 3

5
abcab

Sample Output 3

17



Sample input:
4
abcd


Sample output:
15

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
L = []
cnt = []
for i in range(N):
  if not S[i] in L:
    L.append(S[i])
    cnt.append(1)
  else:
    for j in range(len(L)):
      if L[j] == S[i]:
        cnt[j] += 1
        break
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
ans = 0
n = 2
for X in range(1,2**len(L)):
  k = Base_10_to_n(X, n).zfill(len(L))
  cur = 1
  for i in range(len(k)):
    if k[i] == '1':
      cur *= cnt[i]
  ans += cur
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
DBG = True
n = int(input())
s = input()
cnt = { 'a':0, 'b':0, 'c':0, 'd':0, 'e':0, 'f':0, 'g':0, 'h':0, 'i':0, 'j':0, 'k':0, 'l':0, 'm':0, 'n':0, 'o':0, 'p':0, 'q':0, 'r':0, 's':0, 't':0, 'u':0, 'v':0, 'w':0, 'x':0, 'y':0, 'z':0 }
for i in range(n):
    cnt[s[i]] += 1

prod = 1
for key in cnt:
    prod *= cnt[key] + 1
print(prod-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
s = input()

mod = 10**9 + 7

cnt_dict = Counter(s)
ans = 1
for v in cnt_dict.values():
    ans *= v + 1
ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
S = input()

alp = "abcdefghijklmnopqrstuvwxyz"
x = [1] * 26

for i in range(N):
    x[alp.find(S[i])] += 1

print(np.prod(x)-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import collections 

n=input()
s=input()

d=collections.Counter(s)

#print(d)

ans = 1
for i in d:
    ans *= d[i]+1

print(ans-1)

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
s = input()

memo = {}
for i in range(len(s)):
  if s[i] not in memo:
    memo[s[i]] = 1
  else:
    memo[s[i]] += 1
    
li = []
for i in memo.values() :
  li.append(i)
ans = 0
for i in itertools.product(range(2),repeat=len(li)):
  tmp = 1
  flag = False
  for j in range(len(li)):
    if i[j] != 0:
      flag = True
      tmp *= li[j]
  if flag:
    ans = ans + tmp
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import functools

n = int(input())
s = list(input())
md = 10 ** 9 + 7

c = [x + 1 for x in dict(collections.Counter(s)).values()]
#print(c)
ans = functools.reduce(lambda a, b: a * b, c) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
n=int(input())
s=input()
count=[1 for i in range(26)]
for i in range(n):
    count[ord(s[i])-ord('a')]+=1
print(reduce(lambda a,b:a*b ,count)-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
input()
s=list(input())
if len(set(s))==1:
    print(1)
else:
    c=Counter(s)
    ans=1
    for i in c.values():
        ans*=(i+1)
    ans-=1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
sum = 0
for i in range(N):
  sum += i + 1

print(sum)

Submission status: Wrong Answer

Solution code:
#AGC031-A
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n=I()
S=S()
Sd={}
for s in S:
    if s in Sd:
        Sd[s]+=1
    else:
        Sd[s]=1
one=0
for key in Sd.keys():
    if Sd[key]==1:
        one+=1
ans=2**one-1
for key in Sd.keys():
    if Sd[key]>=2:
        ans+=(ans+1)*Sd[key]
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
S = input()

t = set()
for i in range(1,N+1):
  for c in combinations(S, i):
    t.add(c)
print(len(t))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()

cnt = [0] * 26

for ss in S:
    cnt[ord(ss) - 97] += 1

sum = 1
for c in cnt:
    sum = sum * (c + 1)
print(sum - 1)

Submission status: Wrong Answer

Solution code:
L = [0]*26
N = int(input())
S = input()

for i in range(N):
    temp = ord(S[i]) - ord("a")
    L[temp] += 1

ans = 1
for a in L:
    if a:
        ans *= (a+1)

print(ans-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
alpha = [0 for _ in range(ord("z")-ord("a")+1)]

for i in range(len(s)):
    alpha[ord(s[i])-ord("a")] += 1
# print(alpha)
_sum = alpha[0]+1
for i in range(1, len(alpha)):
    _sum *= alpha[i]+1
print(_sum-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()

a = {}
for i in range(n):
    if s[i] not in a:
        a[s[i]] = 1
    else:
        a[s[i]] += 1
count = 1
for i in a.keys():
    count *= a[i] + 1

print(count-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline

n = int(input())
S = list(input())
dic = {}

for d in S:
    if d not in dic:
        dic[d] = 1
    else:
        dic[d] += 1
tot = 1
for d in dic:
    i = dic[d] + 1
    tot *= i

print((tot-1) % (10**9+7))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
l=list(s)
sl=set(l)

import collections

c=collections.Counter(l)
ans=1
for i in sl:
    ans*=(c[i]+1)

print(ans-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
input()
s=list(input())
c=Counter(s)
ans=1
for i in c.values():
    ans*=(i+1)
ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = str(input())
ss = sorted((set(list(S))))
k = []
for i in range(len(ss)):
	k.append(S.count(ss[i])+1)
tmp = 1
for i in range(len(k)):
	tmp *= k[i]
ans = tmp - 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
s2 = set(s)
s2 = list(s2)
ans = 1
for i in range(len(s2)):
    a = s.count(s2[i])
    ans *= a+1
print(ans-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = str(input())
d ={}
for i in range(n):
  x = s[i]
  if x not in d:
    d[x] = 1
  else:
    d[x] += 1
ans = 1
for a in d.values():
  ans *= a+1
print(ans-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
S = input()

ctr = Counter(S)
ans = 1
for v in ctr.values():
    ans *= (v+1)
print(ans-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
count = {}
for c in s:
    if c not in count:
        count[c] = 1
    else:
        count[c] += 1
ret = 1
for _, c in count.items():
    ret *= c + 1
print(ret - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
Count = 1
for i in range(26):
    letter = chr(97+i)
    Count *= S.count(letter) + 1
print(Count-1)

Submission status: Wrong Answer

Solution code:
import math

n=int(input())
s=input()

l=[]
for i in range(26):
	l.append(0)

for i in range(n):
	l[ord(s[i])-97]+=1

p=1000000007
ans=1
for i in range(26):
	ans*=(l[i]+1)

ans-=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
S = input()
ct = Counter(S)
ans = 1
for k, v in ct.items():
  ans *= v + 1
print(ans - 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in 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 SI(): return input()

def main():
    N = II()
    S = SI()
    global ans
    ans = 1
    from collections import Counter
    cnt = Counter(S)
    for s, n in cnt.items():
        ans *= (n + 1)

    ans -= 1
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()
def stoi(s):
    return ord(s)-97
X = [1] * 26
for ss in s:
    X[stoi(ss)] += 1

ans = 1
P = 10**9+7
for x in X:
    ans *= x % P
print(ans - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
mod = 1e9 + 7
dic =  { i:0  for i in [chr(i) for i in range(97, 97+26)]}
for i in range(N):
    dic[S[i]] += 1

ans = 1
for value in dic.values():
    ans *= (value+1)
print(ans-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()
def stoi(s):
    return ord(s)-97
X = [1] * 26
for ss in s:
    X[stoi(ss)] += 1

ans = 1
for x in X:
    ans *= x
print(ans - 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = input()

char = {}
for c in S:
	if c not in char:
		char[c] = 1
	else:
		char[c] += 1

ans = 1
for c in char:
	ans *= char[c]+1

print(ans-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

N = int(input())
S = input()
c = Counter(S)
ans = 1
for v in c.values():
    ans *= (v + 1)
print(ans - 1)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
count={}
for s in S:
    count[s]=count.get(s,0)+1
retval=1
for c in count:
    retval*=(count[c]+1)
print(retval-1)

Submission status: Wrong Answer

Solution code:
input()
s=input()
d={}
for t in s:d[t]=d.get(t,0)+1
r=1
for k in d.values():r*=k+1
print(r-1)

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
S = input()

d = Counter(S)
ans = 1
for k, v in d.items():
  ans *= v + 1
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
c = [0] * 26
for s in S:
    c[ord(s)-ord('a')] = (c[ord(s)-ord('a')] + 1) % (10**9+7)
import itertools
import operator
from functools import reduce
ans = 0
for j in range(1, 27):
    for i in itertools.combinations(c, j):
        ans += reduce(operator.mul,i) % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from itertools import product

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N = int(input())
    S = input().rstrip()

    c = Counter(S)
    values = list(c.values())
    ans = -1
    for comb in product(range(2), repeat=len(values)):
        res = 1
        for i, c in enumerate(comb):
            if c == 1:
                res = (res * values[i]) % P
        ans = (ans + res) % P

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=list(input())

from collections import*
C=Counter(S)
M=min(26,len(C))

from itertools import*

ans=0
i=1
while i<=M:
    L=list(combinations(C.values(),i))
    j=0
    while j<len(L):
        a=1
        for l in L[j]:
            a=a*l%(10**9+7)
        ans+=a
        ans%=(10**9+7)
        j+=1
    i+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=list(input())

from collections import*
C=Counter(S)
M=min(26,len(C))

from itertools import*

ans=0
i=1
while i<=M:
    L=list(combinations(C.values(),i))
    j=0
    while j<len(L):
        a=1
        for l in L[j]:
            a*=l 
        ans+=a
        ans%=(10**9+7)
        j+=1
    i+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
s=list(input())
c=Counter(s)
c=c.values()
ans=len(s)
mod=10**9+7
for i in range(2,len(c)+1):
    for l in itertools.combinations(c,i):
        res=1
        for j in l:
            res*=j
            res%=mod
        ans+=res
        ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
n = int(input())
s = input()
a = []
ans = 0
def dfs(st, num):
    if num == n:
        global ans, a
        a.append(st)
        ans += 1
        return        
    if s[num] not in st:
        dfs(st + s[num], num+1)
        dfs(st, num+1)
    else:
        dfs(st, num+1)


dfs("", 0)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=str(input())
s=list(s)
import collections
c=collections.Counter(s)
values, counts = zip(*c.most_common())
temp=list(counts)
l=len(temp)
ans=0
for i in range(2**l):
  tt=1
  for j in range(l):
    if ((i >> j) & 1):
      tt=tt*temp[j]
  ans=(ans+tt)%(10**9+7)
print((ans-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=str(input())
s=list(s)
import collections
c=collections.Counter(s)
values, counts = zip(*c.most_common())
temp=list(counts)
l=len(temp)
ans=0
for i in range(2**l):
  t=[]
  for j in range(l):
    if ((i >> j) & 1):
      t.append(temp[j])
  tt=1
  for j in range(len(t)):
    tt=(tt*t[j])%(10**9+7)
  ans=ans+tt
print((ans-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# O(10**8)くらいあるんだけど...
from collections import Counter
from itertools import combinations
MOD = 10**9+7
n = int(input())
s = input()
c = Counter(s)
abc = set(s)
ans = n
for i in range(2, len(abc)+1):
    for comb in combinations(abc, i):
        tmp = 1
        for x in comb:
            tmp *= c[x]
            tmp %= MOD
        ans += tmp
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from functools import reduce
from collections import Counter


MOD = 10 ** 9 + 7
N = int(input())
S = input()
cnt = Counter(S)
ans = 0
for i in range(1, N + 1):
    for cs in combinations("abcdefghijklmnopqrstuvwxyz", i):
        ans += reduce(lambda x, y: x * y, [cnt[c] for c in cs])
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from functools import reduce
from collections import Counter


N = int(input())
S = input()
cnt = Counter(S)
ans = 0
for i in range(1, N + 1):
    for cs in combinations("abcdefghijklmnopqrstuvwxyz", i):
        ans += reduce(lambda x, y: x * y, [cnt[c] for c in cs])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import combinations

MOD = 10**9 + 7

N = int(input())
S = input()
c = Counter(S)

ans = 0

for i in range(1, len(c)+1):
    # i文字の部分文字列を考えると、i種類の文字が使われているので
    for keys in combinations(c.keys(), i):
        res = 1
        for k in keys:
            res *= (c[k])
        ans += res
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
s=s0()

c=Counter(s)
d=list(c.values())
MOD=10**9+7

def prod(line):
    r=1
    for i in line:
        r*=i
        r%=MOD
    return r

i=2
ans=sum(d)
while i<=len(d):
    tmp=itertools.combinations(d,i)
    for line in tmp:
        ans+=prod(line)
    i+=1

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
s=s0()

c=Counter(s)
d=list(c.values())

def prod(line):
    r=1
    for i in line:
        r*=i
    return r

i=2
ans=sum(d)
while i<=len(d):
    tmp=itertools.combinations(d,i)
    for line in tmp:
        ans+=prod(line)
    i+=1

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
def myAnswer(N:int,S:str) -> int:
   counter = 0
   for i in range(1,N+1):
      for p in itertools.combinations(S,i):
         if (len(set(p)) == i):
            counter += 1

   return counter

def modelAnswer():
   return
def main():
   N = int(input())
   S = input()
   print(myAnswer(N,S))
if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

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

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    s = input()

    c = collections.Counter(s)

    ans = 0
    for i in range(1, n + 1):
        for t in itertools.combinations(c.keys(), i):
            tmp = 1
            for ti in t:
                tmp *= c[ti] % MOD
            ans += tmp
            ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import combinations

N = int(input())
S = input()
Q = int(1e9 + 7)

d = defaultdict(int)
keys = set()

for s in S:
    d[s] += 1
    keys.add(s)

ans = 0

for i in range(0, len(keys)):
    for c in combinations(keys, i+1):
        n = 1
        for k in c:
            n *= d[k]
        ans += n
        ans %= Q

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import Counter
  n = int(input())
  s = input()
  mod = 10**9+7
  c = Counter(s)
  cv = list(c.values())
  cl = len(cv)
  ans = 0
  for i in range(1,1<<cl):
    da =1
    for j in range(cl):
      if (i>>j)%2:
        da *= cv[j]
    ans += da%mod
  print(ans%mod)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
s = input()
mod = 10**9+7
c = Counter(s)
cv = list(c.values())
cl = len(cv)
ans = 0
for i in range(1,1<<cl):
  da =1
  for j in range(cl):
    if (i>>j)%2:
      da *= cv[j]
  ans += da%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
mod = 10**9 + 7

ans = 0
G = []
for s in S:
    G.append(s)
    ans += 1
    ans %= mod

    tmp = []
    for g in G:
        if s not in g:
            ans += 1
            ans %= mod
            tmp.append(g+s)
    G += tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from _collections import defaultdict
from itertools import combinations
n=int(input())
S=input()
X=defaultdict(int)
for s in S:
    X[s]+=1
A=0
for i in range(1,len(X.keys())+1):
    for comb in combinations(X.keys(),i):
        ans=1
        for c in comb:
            ans*=X[c]
        A+=ans
print(A%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import itertools as it
MOD = 10 ** 9 + 7
n = int(input())
s = input()

b = Counter(s)
c = list(b)

ans = 0
for i in range(1,len(b)+1):
    d = list(it.combinations(c,i))
    for j in d:
        a = 1
        for k in j:
            a = a*b[k]
            
        ans = (ans+a) %MOD
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 0
for i in range(1, 2**len(d)):
    c = 1
    num = i
    for n, j in d.items():
        if num%2==1:
            c = (c*j)%mod
        num >>= 1
    result = (result+c)%mod

print(result%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in list(s):
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 0
for i in range(1, 2**len(d)):
    c = 1
    num = i
    for n, j in d.items():
        if num%2==1:
            c = (c*j)%mod
        num >>= 1
    result = (result+c)%mod

print(result%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in list(s):
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 0
for i in range(1, 2**len(d)):
    c = 1
    num = i
    for n, j in d.items():
        if num%2==1:
            c *= j
            c %= mod
        num >>= 1
    result += c
    result %= mod

print(result%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in list(s):
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
dic = [j for i, j in d.items()]
result = 0
for i in range(1, 2**len(dic)):
    c = 1
    num = i
    for j in dic:
        if num%2==1:
            c *= j
            c %= mod
        num >>= 1
    result += c
    result %= mod

print(result%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in list(s):
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
dic = [j for i, j in d.items()]
result = 0
for i in range(1, 2**len(dic)):
    c = 1
    n = []
    num = i
    for j in dic:
        if num%2==1:
            c *= j
            c %= mod
            n.append(j)
        else:
            n.append(0)
        num >>= 1
    result += c
    result %= mod

print(result%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())
s = input()
dic = [0 for _ in range(26)]
for i in range(n):
    dic[ord(s[i])-97] += 1
dic = [i for i in dic if i > 0]
result = 0
for i in range(1, 2**len(dic)):
    c = 1
    n = []
    num = i
    for j in dic:
        if num%2==1:
            c *= j
            c %= mod
            n.append(j)
        else:
            n.append(0)
        num >>= 1
    result += c
    result %= mod

print(result%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)

N = int(input())
S = input()
MOD = 10**9 + 7

def dp(i, a, used):
    if i == N-1:
        if S[i] in used:
            return a % MOD
        else:
            return (2*a) % MOD
    else:
        if S[i] in used:
            return dp(i+1, a, used) % MOD
        else:
            return (dp(i+1, a, used) + dp(i+1, a, used|set(S[i]))) % MOD

print(dp(0, 1, set())-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)

N = int(input())
S = input()
MOD = 10**9 + 7

def dp(i, a, used):
    if i == N-1:
        if S[i] in used:
            return a
        else:
            return 2*a
    else:
        if S[i] in used:
            return dp(i+1, a, used)
        else:
            return dp(i+1, a, used) + dp(i+1, a, used|set(S[i]))

print(dp(0, 1, set())-1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations


MOD = 1000000007

N = int(input())
S = input()

chars = set()
cnt = {}
for s in S:
    if s not in chars:
        chars.add(s)
        cnt[s] = 1
    else:
        cnt[s] += 1

ans = N % MOD
r = 2
chars = list(chars)
while r <= len(chars):
    combs = combinations(chars, r)
    for comb in combs:
        res = 1
        for c in comb:
            res *= cnt[c]
            res %= MOD
        ans += res
        ans %= MOD
    r += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())

t = 0
import itertools
for i in range(1,n+1):
    for v in itertools.combinations(s, i):
        if len(v) == len(set(v)):
            t += 1
print(t)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

from collections import Counter
from itertools import combinations

N = int(input())
S = input()

cnter = Counter(S)
alpha = set(cnter)

ans = 0

for i in range(1, len(alpha) + 1):
    if i == 1:
       ans += len(S)
    else:
        for pat in combinations(alpha, i):
            ans += np.prod([value for key, value in cnter.items() if key in pat])

print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import combinations

N = int(input())
S = input()

cnter = Counter(S)
alpha = set(cnter)

ans = 0

for i in range(1, len(alpha) + 1):
    if i == 1:
       ans += len(S)
    else:
        for pat in combinations(alpha, i):
            tmp = 1
            for v in pat:
                tmp *= cnter[v]
            ans += tmp

print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

subs = []
for s0 in reversed(S):
    subs += [s0] + [s0 + s for s in subs if s0 not in s]

ans = len(subs) % (1000000000 + 7)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

def solve(n, A, index):
    if n == 1:
        s = 0
        for i in range(index, len(A)):
            s += A[i][1]
        # print(index, A[index:], s)
        return s
    ans = 0
    for i in range(index, len(A)):
        a = A[i]
        ans = (ans + a[1] * solve(n - 1, A, i + 1)) % mod
    return ans

def main():
    N = int(input())
    S = input()
    num_chars = 0
    A = {}
    for s in S:
        if s not in A:
            A[s] = 0
            num_chars += 1
        A[s] += 1
    # print(num_chars, A)
    B = [(a, A[a]) for a in A]

    ans = 0
    for i in range(num_chars):
        ans = (ans + solve(i + 1, B, 0)) % mod
        # print(ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
dict = {ch : S.count(ch) for ch in S}
ans = 1

for value in dict.values():
    ans *= (value+1)
print((ans-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
import collections
import bisect
table=collections.defaultdict(list)
mod=10**9 +7
for i in range(N):
  table[S[i]].append(i)
ans=0
q=collections.deque()
for i,x in enumerate(S):
  q.append((i,set([x])))
  ans+=1
  while(q):
    id,s=q.popleft()
    for z in table:
      if z in s:
        continue
      else:
        k=bisect.bisect_left(table[z],id)
        if k!= len(table[z]):
          for i in range(k,len(table[z])):
            q.append((table[z][i], s|{z}))
            ans+=1
          ans%=mod               
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
import collections
import bisect
table=collections.defaultdict(list)
mod=10**9 +7
for i in range(N):
  table[S[i]].append(i)
ans=0
q=collections.deque()
for x in table:
  for y in table[x]:
    q.append((y,set([x])))
    ans+=1
    while(q):
      id,s=q.popleft()
      for z in table:
        if z in s:
          continue
        else:
          k=bisect.bisect_left(table[z],id)
          if k!= len(table[z]):
            for i in range(k,len(table[z])):
              q.append((table[z][i], s|{z}))
              ans+=1
            ans%=mod               
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

iCnt = int(input())
v = list(input())

vAns = []
vProduct = []
iOnIndex = 0
for _ in range(iCnt - 1):
    iLen = len(v[-iCnt + iOnIndex + 1:])
    vProduct = itertools.product([0, 1], repeat=iLen)
    for p in vProduct:
        sChk = v[iOnIndex]
        iP_Len = len(p)
        for i in range(iP_Len):
            if p[i] == 1:
                if v[iOnIndex + i + 1] not in sChk:
                    sChk += v[iOnIndex + i + 1]
                else:
                    sChk = "NG"
                    break
        if "NG" not in sChk: vAns.append(sChk)
    iOnIndex += 1
vAns.append(v[iCnt - 1])
print(len(vAns) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import itertools

iCnt = int(input())
v = list(input())

vAns = []
vProduct = []
iOnIndex = 0
while iOnIndex + 1 < iCnt:
    iLen = len(v[-iCnt + iOnIndex + 1:])
    vProduct = list(itertools.product([0, 1], repeat=iLen))
    for p in vProduct:
        sChk = v[iOnIndex]
        iP_Len = len(p)
        for i in range(iP_Len):
            if p[i] == 1:
                if v[iOnIndex + i + 1] not in sChk:
                    sChk += v[iOnIndex + i + 1]
                else:
                    sChk = "NG"
                    break
        if "NG" not in sChk: vAns.append(sChk)
    iOnIndex += 1
vAns.append(v[iCnt - 1])
print(len(vAns) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import itertools

iCnt = int(input())
v = list(input())

vAns = []
vProduct = []
iOnIndex = 0
while iOnIndex + 1 < len(v):
    iLen = len(v[-len(v) + iOnIndex + 1:])
    vProduct = list(itertools.product([0, 1], repeat=iLen))
    for p in vProduct:
        sChk = v[iOnIndex]
        for i in range(len(p)):
            if p[i] == 1:
                if v[iOnIndex + i + 1] not in sChk:
                    sChk += v[iOnIndex + i + 1]
                else:
                    sChk = "NG"
                    break
        if "NG" not in sChk: vAns.append(sChk)
    iOnIndex += 1
vAns.append(v[len(v) - 1])
print(len(vAns) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import itertools

iCnt = int(input())
v = list(input())

vAns = []
vProduct = []
iOnIndex = 0
while iOnIndex + 1 < len(v):
    iLen = len(v[-len(v) + iOnIndex + 1:])
    vProduct = list(itertools.product([0, 1], repeat=iLen))
    for p in vProduct:
        sChk = v[iOnIndex]
        for i in range(len(p)):
            if p[i] == 1:
                if v[iOnIndex + i + 1] not in sChk:
                    sChk += v[iOnIndex + i + 1]
                else:
                    sChk = "NG"
        if "NG" not in sChk: vAns.append(sChk)
    iOnIndex += 1
vAns.append(v[len(v) - 1])
print(len(vAns) % (10 ** 9 + 7))