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: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(10**7)

ans = []


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    #print(S, N)

    #% (10^9 + 7)
    #return count_0
    N_l = len(N)
    for i in range(N_l):
        b(N, N[i], i)
    #print(list(set(ans)))
    #print(10**9 + 7)

    # 2
    #return len(list(set(ans))) % (10**9 + 7)
    for i in range(N_l):
        ans.append(N[i])
    #print(ans)
    return len(ans) % (10**9 + 7)


def b(org_array, temp, i):
    if len(org_array)-1 == i:
        return
    else:
        #print("org array:"+org_array)
        #ans.append(temp)
        #print(temp)
        if org_array[i+1] not in temp:
            b(org_array, temp, i+1)
            temp += org_array[i+1]
            ans.append(temp)
        #print("org: "+org_array[i+1])
        #print(temp)
        b(org_array, temp, i+1)


def main():
    input_line = stdin.readlines()
    answer = problem_a(input_line)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
import numpy as np

N=int(input())
S=list(input())
answer=0
col = collections.Counter(S)
values, counts = zip(*col.most_common())

for i in range(N):
    C=list(itertools.combinations(counts, i+1))
    kumiawase=[np.prod(j) for j in C]
    answer=(answer+sum(kumiawase))%(7+10**9)
print(answer)

Submission status: Time Limit Exceeded

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

result = 0
route = []
abc = 'abcdefghijklmnopqrstuvwxyz'
for i in range(len(abc)):
    co = S.count(abc[i])
    if co > 0:
        route.append(co)

for i in range(1,len(route)+1):
    xxx = result
    #i種類取り出して掛け算した値を足し込む
    for cb in itertools.combinations(route, i):
        num = 1
        for x in cb:
            num = num * x
        result += num
    if xxx == result:
        break
print(result%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def sub_sequence(l):
    if len(l) <= 1:
        return len(l)
    else:
        cnt = 0
        for i, c in enumerate(l):
            sub = [x for x in l[i:] if x != c]
            cnt += 1
            cnt += sub_sequence(sub)
        return cnt


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

print(sub_sequence(s) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n=int(input())
s=input()
ans=0
set_s=len({i for i in s})
for i in range(1,set_s+1):
    koho=tuple(combinations(s,i))
    ex=tuple([j for j in koho if len(j)==len(tuple(set(j)))])
    ans+=len(ex)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

d = {i: s.count(i) for i in k}

counta=0
for i in k:
    counta+=s.count(i)



for i in range(2,len(k)+1):
    li=list(itertools.combinations(k,i))    
    for h in li:
        z="".join(h)
        q=d[z[0:(len(h)-1)]]*d[z[-1]]
            
        d[z]=q
        counta+=q
    
print(counta%(10**9+7))

Submission status: Time Limit Exceeded

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

ans = 0
a = 10**9 + 7

nunique = len(set(S))
for i in range(1, nunique+1):
    for t in combinations(S, i):
        if len(t) == len(set(t)):
            ans += 1
            
print(ans % a)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 16 22:09:20 2019

@author: iwata
"""

import itertools
from operator import mul
from functools import reduce


N = input()
S = input()

Sset = list(set(S)) 
Sset1 = []

a = 0

for i in range(len(Sset)):
    num = S.count(Sset[i])
    Sset1.append(num)

for j in range(len(Sset)):
    com =  list(itertools.combinations(Sset1, j+1))
    for k in range(len(com)):
        a = a + reduce(mul, com[k])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product

N = int(input())
S = input().strip()
dic = Counter(S)
mod = 10**9 + 7

ans = []
ls =list(product([0, 1], repeat=len(dic)))
ls.pop(0)

a = []
for i in dic:
    a.append(dic[i])

for x in ls:
    num = 1
    for z, y in zip(a, x):
        if y == 1:
            num = (z*num)%mod
    ans.append(num)
print(sum(ans)%mod)

Submission status: Time Limit Exceeded

Solution code:
#%%
import itertools

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

unique = {}
for c in S:
    try:
        unique[c] += 1
    except:
        unique[c] = 1


#%%

def fact(n):

    if n in fact_memo:
        return fact_memo[n]

    else:
        new = (n * fact(n-1)) % MOD
        fact_memo[n] = new
        inv_memo[n] = modinv(new, MOD)
        return new

def egcd(a, b):
    x, lastx = 0, 1
    y, lasty = 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, lastx = lastx - q * x, x
        y, lasty = lasty - q * y, y
    return lastx, lasty, a

def modinv(a, m):
    inv, q, gcd_val = egcd(a, m)
    return inv % m


ans = 0

for i in range(1,len(unique)+1):
    for item in itertools.combinations(unique.keys(), i):

        patterns = 1
        for alphabet in item:
            patterns = (patterns * unique[alphabet]) % MOD
    
        ans = (ans + patterns) % MOD
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

#文字数ごとに探索
cnt = len(s)

def calcPatternsNum(s, num_letter):
  if num_letter == 0:
    return 1
  elif len(s) == 0:
    return 0
  num_patterns = 0
  for i, nextLetter in enumerate(s):
    s_sub = s[i+1:].replace(nextLetter, "")
    num_patterns += calcPatternsNum(s_sub, num_letter - 1)
  return num_patterns
 
for length in range(2, min(len(s), 26) + 1):
  cnt += calcPatternsNum(s, length)
  
print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0
a = 10**9 + 7

for i in range(1, 27):
    for t in combinations(S, i):
        if len(t) == len(set(t)):
            ans += 1
            
print(ans % a)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

d = {}
for i,n in enumerate(S):
    if n in d.keys():
        d[n] += 1
    else:
        d[n] = 1

count = 0
for i in range(1,len(d.keys())+1):
    for p in list(itertools.combinations(d.keys(),i)):
        tmp = 1
        for c in p:
            tmp *= d[c]
        count += tmp
        count %= D
print(count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n=int(input())
s=input()
ans=0
set_s=len({i for i in s})
for i in range(1,set_s+1):
    koho=tuple(combinations((j for j in s),i))
    ex=tuple([j for j in koho if len(j)==len(tuple(set(j)))])
    ans+=len(ex)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = input()
N = int(n[0])

st = input()
S = list(st)

count = 0
for i, _ in enumerate(S, 1):     
    for j in itertools.combinations(S, r=i):
        if len(j) == len(set(j)):
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

m = len(set(s))
count = 0

for i in range(m):
    strings = itertools.combinations(s, i+1)
    tmp = [1 for string in strings if len(set(string)) == i+1]
    count += len(tmp)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

ans = 0
a = 10**9 + 7

for i in range(1, len(str(S))+1):
    for t in combinations(S, i):
        if len(t) == len(set(t)):
            ans += 1
            
print(ans % a)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count = N

for n in range(1, N):
  comb = list(itertools.combinations(S, n + 1))

  c = 0
  for sub_s in comb:
    if len(set(sub_s)) == n + 1:
      c += 1

  count += c

print(count % int(pow(10, 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product

N = int(input())
S = input().strip()
dic = Counter(S)
mod = 10**9 + 7

ans = 0
ls =list(product([0, 1], repeat=len(dic)))
ls.pop(0)

a = []
for i in dic:
    a.append(dic[i])

for x in ls:
    num = 1
    for z, y in zip(a, x):
        if y == 1:
            num = (z*num)%mod
    ans = (ans+num)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
s = input()
cnt = 0
for i in range(1,n+1):
    for v in itertools.combinations(s, i):
        if len(v)==len(set(v)):
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = input()
N = int(n[0])

st = input()
S = list(st)

count = 0
for i, _ in enumerate(S, 1):     
    for j in itertools.combinations(S, r=i):  # rには1、2、3と渡される
        seq = list(j)
        if len(seq) == len(set(seq)):
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count = 0
for i in range(n):
    strings = itertools.combinations(s, i+1)
    tmp = [1 for string in strings if len(set(string)) == i+1]
    count += len(tmp)

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count = 0
for n in range(N):
  comb = list(itertools.combinations(S, n + 1))

  c = 0
  for sub_s in comb:
    if len(set(sub_s)) == len(sub_s):
      c += 1

  count += c

print(count % int(pow(10, 9) + 7))

Submission status: Time Limit Exceeded

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

cache = {}
for i in range(N):
    if S[i] in cache:
        cache[S[i]].append(i)
    else:
        cache[S[i]] = [i]

result = 0
route = []
for k,v in cache.items():
    route.append(len(v))
for i in range(1,28):
    xxx = result
    #i種類取り出して掛け算した値を足し込む
    for cb in itertools.combinations(route, i):
        num = 1
        for x in cb:
            num = num * x
        result += num
    if xxx == result:
        break
print(result%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

setS = S	

ans = 0
for i in range(1,len(setS)+1):
	e = list(itertools.combinations(setS, i))
	for t in e:
		t2 = "".join(t)
		if len(t2) == len(set(t2)):
			#print(t2)
			ans += 1
	
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
sum = 0
mod = 10**9 + 7

n = int(input())
moji = {}
for c in list(input()):
  if not c in moji.keys():
    moji[c] = 1
  else:
    moji[c] += 1

moji_value = list(moji.values())
    
for length in range(1, len(moji)+1):
  for combi in itertools.combinations(range(len(moji)),length):
    temp_sum = 1
    for i in combi:
      temp_sum *= moji_value[i]
    sum = (sum + temp_sum) % mod
    
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = [str(c) for c in input().strip()]

    ans = 0
    SS = []
    for i in range(N):
        si = S[i]
        d = {}
        for j in S[i+1:]:
            if j == si:
                continue
            if j in d:
                d[j] += 1
            else:
                d[j] = 1

        t = 1
        for k in d:
            t *= d[k] + 1

        ans += t

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0
mod = 10**9 + 7

def dfs(st, i):
    global ans
    # print("st:{} i:{} ans:{}".format(st,i,ans))
    for n in range(i, len(S)):
        if not S[n] in st:
            ans = ans % mod + 1
            dfs(st+S[n], n+1)
    return ans
    
print(dfs('', 0))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 16 21:00:45 2019

@author: iwata
"""
import itertools

N = input()
S = input()

Sset = list(set(S)) 
Sset1 = []

a = 0
b = 0

for i in range(len(Sset)):
    num = S.count(Sset[i])
    Sset1.append(num)

for j in range(len(Sset)):
    com =  list(itertools.combinations(Sset1, j+1))
    for k in range(len(com)):
        for l in range(j+1):
            if l == 0:
                a = a + com[k][l]
            else:
                a = a * com[k][l]
        b = b + a
        a = 0

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

res = 0
for i in np.arange(1, n+1, 1):
    acc = 0
    tmp = list(itertools.combinations(s, i))
    for i,t in enumerate(tmp):
        if len(t) != len(set(t)):
            acc += 1
    res += len(tmp) - acc
print(res % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import itertools
from functools import reduce


def analyze(string):
  s_count = defaultdict(int)
  for s in string:
    s_count[s] += 1
  counts = list(s_count.values())
  return counts

def count(counts, num_set):
    if num_set == 1:
        return sum(counts)
    if num_set == 2:
        num_sum = sum(counts)
        ans = 0
        for i in range(len(counts)):
            num_sum -= counts[i]
            ans += counts[i] * num_sum
        return ans

    ans = 0
    for i in range(len(counts) - 1):
        ans += counts[i] * count(counts[i + 1:], num_set - 1)
    return ans

N = int(input())
string = input()

counts = analyze(string)
ans = 0
for i in range(1, len(counts) + 1):
    ans += count(counts, i)
print(ans % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import itertools

def is_unique(ls):
    return len(ls) == len(set(ls))

n = int(input())
s = input()
result = 0
for i in range(n):
    for j in itertools.combinations(s,i+1):
        result += 1 if is_unique(j) else 0
print(result)

Submission status: Time Limit Exceeded

Solution code:
def f(s, n, a):
    c = 1
    for i in range(n):
        if not s[i] in a:
            c += f(s[i+1:], n-i-1, a+s[i])
    return c


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

print(f(S, N, "")-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
num = 10 ** 9 + 7

i = 0
out_lst = [""]
cnt = 0

while len(out_lst[-1]) < 26 and i < len(s):
    for elem in out_lst:
        if not s[i] in elem:
            elem += s[i]
            out_lst.append(elem)
        else:
            cnt += 1
    i += 1

print(len(out_lst) - 1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
S = input()
ans = 0
s = [x for x in S]
for i in range(1,N+1):
    ans2=0
    for x in list(itertools.combinations(s,i)): 
        dup = [y for y in s if x.count(y)>1]
        if dup!=[]:
            for z in set(dup):
                if x.count(z)==1:
                    ans2+=1
        else:
            ans2+=1
    ans+=ans2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product

N = int(input())
S = input().strip()
dic = Counter(S)
mod = 10**9 + 7

ans = 0
ls =list(product([0, 1], repeat=len(dic)))
ls.pop(0)

for x in ls:
    num = 1
    for z, y in zip(dic, x):
        if y == 1:
            num = (dic[z]*num)%mod
    ans = (ans+num)%mod
print(ans)

Submission status: Time Limit Exceeded

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

ans = N
Q = [[i] for i in range(N)] 
L = 2
while Q and L<27:
    Q_tmp = []
    for q in Q:
        tmp = ""
        for c in q:
            tmp += S[c]
        for i in range(q[-1]+1,N):
            if not(S[i] in tmp):
                Q_tmp.append(q+[i])
                ans += 1
        ans %= 10**9+7
    Q = Q_tmp
    L += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=1000000007

n=int(input())#整数
s=input()#文字列
s_list=list(s)#リスト

alphabet=["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
count=0
for i in range(2**n):
    bubunretsu=[]
    flag=1
    for j in range(n):
        if (i>>j)&1:
            bubunretsu.append(s_list[j])

    for j in range(len(alphabet)):
        number=bubunretsu.count(alphabet[j])
        if number>=2:
            flag=0

    if flag:
        count=count+1

print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N = int(input())
S = input()
Su = sorted(set(S), key=S.index)
cnt = 0
Nu = len(Su)

for i in range(1,Nu+1,1):
    for v in combinations(Su, i):
        tempcnt = 1
        for j in range(len(v)):
            tempcnt *= S.count(v[j])
        cnt += tempcnt

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

num = int(input())
x = input()
cnt = len(x)
for i in range(2,num+1):
  ls = itertools.combinations(x, i)
  for j in ls:
    if len(j) == len(set(j)):
      cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())

dic = {}
for a in input():
    if not a in dic:
        dic[a] = 0
    dic[a] += 1
s = []
for k, v in dic.items():
    s.append([k, v])

total = 0
for i in range(1, len(s) + 1):
    ls = list(itertools.combinations(s, i))
    sub_total = 0
    for cmb in ls:
        num = 1
        for elm in cmb:
            num *= elm[1]
        sub_total += num
    total += sub_total

modulo = 10 ** 9 + 7
print(total % modulo)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n=int(input())
s=input()
ans=0
set_s=len(set([i for i in s]))
for i in range(1,set_s+1):
    koho=tuple(combinations((j for j in s),i))
    for j in koho:
        if len(j)==len(tuple(set(j))):
            ans+=1
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
L = [chr(ord('a') + i) for i in range(26)]
cnt = [0]*26
for i in range(len(S)):
  cnt[ord(S[i])-97] += 1
D = []
for i in range(26):
  if cnt[i] != 0:
    D.append(cnt[i])
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(D)):
  k = Base_10_to_n(X, n).zfill(len(D))
  cur = 1
  for i in range(len(k)):
    if k[i] == '1':
      cur *= (D[i]%(10**9+7))
  ans += (cur%(10**9+7))
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product

N = int(input())
S = input().strip()
dic = Counter(S)
mod = 10**9 + 7

ans = 0
ls =list(product([0, 1], repeat=len(dic)))
ls.pop(0)

for x in ls:
    num = 1
    for z, y in zip(dic, x):
        if y == 1:
            num = dic[z]*num
            num = num%mod
    ans += num
    ans = ans%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count = 0
for i in range(n):
    strings = itertools.combinations(s, i+1)
    for string in strings:
        if len(set(string)) == i+1:
            count += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = input()
S = input().strip()
type = len(set(S))

def DP(i,s):
  # 葉チェック
  if i >= len(S):
    return 1 if len(s) > 0 else 0
  if len(s) >= type:
    return 1
  if i+1 == len(S):
    adopt = 1 if S[i] not in s else 0
    me = 1 if len(s) > 0 else 0
    return adopt + me
  
  # S[i]を採用しない枝
  notadopt = DP(i+1, s)
  
  # S[i]を採用する枝
  if S[i] not in s:
    s += S[i]
    adopt = DP(i+1, s)
  else:
    adopt = 0

  return adopt + notadopt

print(DP(0, '')%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

#文字数ごとに探索
cnt = len(s)

for length in range(2, min(len(s), 26) + 1):
  # patterns = list(itertools.combinations(s, length))
  patterns = [pattern for pattern in itertools.combinations(s, length) if len(pattern) == len(set(pattern))]
  # print(patterns)
  cnt += len(patterns)
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
L = [chr(ord('a') + i) for i in range(26)]
cnt = [0]*26
for i in range(len(S)):
  cnt[ord(S[i])-97] += 1
D = []
for i in range(26):
  if cnt[i] != 0:
    D.append(cnt[i])
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(D)):
  k = Base_10_to_n(X, n).zfill(len(D))
  cur = 1
  for i in range(len(k)):
    if k[i] == '1':
      cur *= D[i]
  ans += cur
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
num = 10**9+7
count = 0
for i in range(N):
  tmp = S[i]
  list_ = [tmp]
  for j in range(i+1,N):
    if S[j] != tmp:
      for k in range(len(list_)):
        if S[j] not in list_[k]:
          list_.append(list_[k]+S[j])
  count+=len(list_)
print(count%num)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=list(input())
import itertools
num=0
for i in range(N):
    c = list(itertools.combinations(S, i+1))
    for v in c:
        v=list(v)
        v.sort()
        C=''.join(v)
        a=(list(set(C)))
        a.sort()
        if C==''.join(a):
            num=num+1
print(num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
L = [chr(ord('a') + i) for i in range(26)]
cnt = [0]*26
for i in range(len(S)):
  cnt[ord(S[i])-97] += 1
D = []
for i in range(26):
  if cnt[i] != 0:
    D.append(cnt[i])
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(D)):
  k = Base_10_to_n(X, n).zfill(len(D))
  cur = 1
  for i in range(len(k)):
    if k[i] == '1':
      cur *= D[i]
  ans = (ans+cur)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def is_unique(ls):
    return len(ls) == len(set(ls))

n = int(input())
s = input()
result = []
for i in range(n):
    tmp = list(itertools.combinations(s,i+1))
    result += list(filter(lambda x:is_unique(x),tmp))
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

modulo = 10 ** 9 + 7

dic = {}
for a in s:
    if not a in dic:
        dic[a] = 0
    dic[a] += 1
shortened = []
for k, v in dic.items():
    shortened.append([k, v])

total = 0
for i in range(1, len(shortened) + 1):
    ls = list(itertools.combinations(shortened, i))
    sub_total = 0
    for cmb in ls:
        num = 1
        for elm in cmb:
            num *= elm[1]
        sub_total += num
    total += sub_total
print(total % modulo)

Submission status: Time Limit Exceeded

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

tmp = [S[0], '']

for s in S[1:]:

    length = len(tmp)

    for i in range(length):
        if len(tmp[i]) < 26 and s not in tmp[i]:
            tmp.append(tmp[i]+s)

print((len(tmp)-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def f(s, n, a):
    if n == 0 and len(a) == 1:
        return 0
    c = 1
    for i in range(n):
        if not s[i] in a:
            c += f(s[i+1:], n-i-1, a+s[i])
    return c


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

print(f(S, N, ""))

Submission status: Time Limit Exceeded

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

d = {i: s.count(i) for i in k}



counta=0

for i in range(1,len(k)+1):
    li=list(itertools.combinations(k,i))

    
    for h in li:
        q=1
        for l in h:
            q*=d[l]
     
        counta+=q
    
print(counta%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n=int(input())
s=input()
ans=0
set_s=len(set([i for i in s]))
for i in range(1,set_s+1):
    koho=tuple(combinations([j for j in s],i))
    for j in koho:
        if len(j)==len(tuple(set(j))):
            ans+=1
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
n=int(input())
s=list(str(input()))
c=collections.Counter(s)
alph_num=len(c.values())
ans=0
for i in range(alph_num):
    testlist=list(itertools.combinations(s,i+1))
    for seg in testlist:
        c_test=collections.Counter(seg)
        if len(c_test.values())==i+1:
            ans+=1
        else:
            pass
print(int(ans%(1e+9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

#文字数ごとに探索
cnt = 0

for length in range(1, min(len(s), 26) + 1):
  # patterns = list(itertools.combinations(s, length))
  patterns = [pattern for pattern in itertools.combinations(s, length) if len(pattern) == len(set(pattern))]
  # print(patterns)
  cnt += len(patterns)
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
def dfs(start, used, n):
    count = 0
    used = used.copy()
    for i in range(start, len(S)):
        if len(used)+len(S)-i < n:
            break
        if S[i] in used:
            continue
        else:
            used.add(S[i])
            if len(used) == n:
                count += 1
            else:
                count += dfs(i+1, used, n)
            used.remove(S[i])
    return count
ans = 0
for i in range(N):
    ans += dfs(0, set(), i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

d = {}
for i,n in enumerate(S):
    if n in d.keys():
        d[n] += 1
    else:
        d[n] = 1

count = 0
for i in range(1,len(d.keys())+1):
    for p in list(itertools.combinations(d.keys(),i)):
        tmp = 1
        for c in p:
            tmp *= d[c]
        count += tmp
print(count%D)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m
    
    def add(self, a, b):
        return (a + b ) % self.m

    def sub(self, a, b):
        return (a - b) % self.m
    
    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, self.pow(b, self.m-2))

    def pow(self, x, y):
        if y == 0: 
            return 1
        elif y == 1: 
            return x % self.m
        elif y % 2 == 0: 
            return self.pow(x, y//2)**2 % self.m
        else: 
            return self.pow(x, y//2)**2 * x % self.m



@mt
def slv(N, S):

    ans = 0
    CC = Counter()
    for c in S:
        CC[c] += 1
    
    m = Mod(10**9+7)

    cs = tuple(CC.values())
    def f(v):
        if not v:
            return 1
        
        c = v[0]
        v = v[1:]
        return m.add(m.mul(c, f(v)), f(v))
    return f(cs) - 1


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = input()
S = input().strip()
type = len(set(S))

def DP(i,s):
  # 葉チェック
  if i >= len(S):
    return 1 if len(s) > 0 else 0
  if len(s) >= type:
    return 1
  
  # S[i]を採用しない枝
  notadopt = DP(i+1, s)
  
  # S[i]を採用する枝
  if S[i] not in s:
    s += S[i]
    adopt = DP(i+1, s)
  else:
    adopt = 0

  return adopt + notadopt

print(DP(0, '')%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N=int(input())
S=list(input())
answer=0

def is_unique(seq):
    return len(seq) == len(set(seq))

for i in range(N):
    C=list(itertools.combinations(S, i+1))
    C=[j for j in C if is_unique(j)]
    answer+=len(C)
print(answer%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

#文字数ごとに探索
cnt = 0

for length in range(1, max(len(s), 26) + 1):
  patterns = list(itertools.combinations(s, length))
  patterns = [pattern for pattern in patterns if len(pattern) == len(set(pattern))]
  # print(patterns)
  cnt += len(patterns)
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import itertools

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

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

sum = 0
for i in range(len(alphabet_map.keys())):
    for comb in itertools.combinations(list(alphabet_map.keys()), i + 1):
        tmp = 1
        for x in comb:
            tmp *= alphabet_map[x]
        sum += tmp
print(sum % (1000000000 + 7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Dict = {}

import itertools

for i in range(N):
	if S[i] in Dict:
		Dict[S[i]] = Dict[S[i]] + 1
	else:
		Dict[S[i]] = 1

count = 0

L = len(Dict)
seq = Dict.keys()

for i in range(L):
	for lis in list(itertools.combinations(seq,i+1)):
		add = 1
		for key in lis:
			add = add * Dict[key]
		count = count + add
		count = count%(10**9 + 7)

print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
import itertools

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

ans = 0

for i in range(1,N+1):
  tmp_s_list = list(itertools.combinations(S,i))
  tmp_s_dict = collections.Counter(tmp_s_list)
  for key in tmp_s_dict:
    if max(collections.Counter(key).values()) == 1:
      ans += tmp_s_dict[key]

print(int(ans % (1e9 + 7)))