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: Runtime Error

Solution code:
import itertools
import numpy as np
import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)

N = int(input())
S = list(input())  # len:N

S = sorted(S)  #  アルファベット順に並べ替え
U = [0] * 26  #  ユニーク数数え上げ
tmp = "0"
count = 0
u_count = 0
for i in range(N):
    if i > 0:
        if tmp == S[i]:
            U[count] += 1
        else:
            tmp = S[i]
            count += 1
            U[count] += 1
    else:
        tmp = S[i]
        U[count] += 1


for u in range(26):
    if U[u] != 0:
        u_count += 1

U = sorted(U)

for i in range(len(U)):
    if U[0] == 0:
        U.pop(0)

count = 0

for i in range(1, u_count+1):
    count += np.sum(np.array((map(prod, list(itertools.combinations(U, i))))))

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

Submission status: Runtime Error

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


def main():
  n = int(input())
  prev = -1
  nums = []
  table = {}

  for _ in range(n):
    v = int(input())

    if v != prev:
      nums.append(v)
      prev = v

  for i, n in enumerate(nums):
    if n not in table:
      table[n] = []

    table[n].append(i)

  values = [0] * len(nums)
  value = 1

  for i in range(len(nums)):
    values[i] += value

    for j in table[nums[i]]:
      if j <= i:
        continue

      values[j] += value

    value = values[i]

  print(value % int(1e+9 + 7), flush=True)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

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


def main():
  n = int(input())
  prev = -1
  nums = []
  table = {}

  for _ in range(n):
    v = int(input())

    if v != prev:
      nums.append(v)
      prev = v

  for i, n in enumerate(nums):
    if n not in table:
      table[n] = []

    table[n].append(i)

  values = [0] * len(nums)
  value = 1

  for i in range(len(nums)):
    values[i] += value

    for j in table[nums[i]]:
      if j <= i:
        continue

      values[j] += value

    value = values[i] % int(1e+9 + 7)

  print(value, flush=True)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

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

used_list = []
num = 0
a = 10**9 +7 

def DFS(i,used_list,num):
    if i == N:
        num += 1
        return num % a

    s = S[i]
    # S[i]を使わない場合
    num = DFS(i+1,used_list,num)

    # S[i]を使う場合
    if s not in used_list:
        used_list.append(s)
        num=DFS(i+1,used_list,num)

        used_list.pop(-1)
    return num % a
    
       
ans = DFS(0,used_list,num)
ans = (ans-1) % a

print(ans)

Submission status: Runtime Error

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

used_list = []
num = 0
a = 10**9 +7 

def DFS(i,used_list,num):
    if i == N:
        num = num % a
        num += 1
        return num

    s = S[i]
    # S[i]を使わない場合
    num = DFS(i+1,used_list,num)

    # S[i]を使う場合
    if s not in used_list:
        used_list.append(s)
        num=DFS(i+1,used_list,num)

        used_list.pop(-1)
    return num
    
       
ans = DFS(0,used_list,num)
ans = ans % a

print(ans-1)

Submission status: Runtime Error

Solution code:
import sys,itertools
input = sys.stdin.readline
N = int(input().strip())
S = input().strip()

le = [S.count(s) for s in set(S)]
cnt = 0
for i in range(len(le)):
    for s in itertools.combinations(le,i+1):
        t=1
        for tt in [x for x in s if x > 1]:
            t*=tt
        cnt+=t
print(cnt%((10**9)+7)

Submission status: Runtime Error

Solution code:
import numpy as np

MOD = 10**9 + 7

matching = {"a":0,"b":1,"c":2,"d":3,"e":4,"f":5,"g":6,"h":7,"i":8,"j":9,"k":10,"l":11,"m":12,\
    "n":13,"o":14,"p":15,"q":16,"r":17,"s":18,"t":19,"u":20,"v":21,"w":22,"x":23,"y":24,"z":25}
inv_matching = dict((v, k) for k, v in matching.items())

def add(a,b):
    c = a+b
    if (c >= MOD):
        c = c - MOD
    return c

def calcnext(strings):
    length = len(strings)
    res = np.full((length+1,26),len(strings),dtype=int)
    for i in reversed(range(length)):
        for j in range(26):
            res[i][j] = res[i+1][j]
        res[i][matching[strings[i]]]= i
    return res

def main():
    length = int(input())
    strings = input()

    nexts = calcnext(strings)

    dp = np.zeros(length+1,dtype=int)
    dp[0] = 1
    tmp = nexts
    for i in range(length):
        for j in range(26):
            if (nexts[i][j] >= length):
                continue
            dp[nexts[i][j] + 1] = add(dp[nexts[i][j] + 1], dp[i])
            nexts[:][j] = length
        nexts = tmp
    print(nexts)
    print(dp)
    result = 0
    dp[0] = 0
    for i in range(length+1):
        result = add(result,dp[i])
    print(result)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

used_list = []
num = 0

def DFS(i,used_list,num):
    if i == N:
        num += 1
        return num

    s = S[i]
    # S[i]を使わない場合
    num = DFS(i+1,used_list,num)

    # S[i]を使う場合
    if s not in used_list:
        used_list.append(s)
        num=DFS(i+1,used_list,num)
        if len(used_list)>0:
            used_list.pop(-1)
    return num
    
       
ans = DFS(0,used_list,num)
print(ans-1)

Submission status: Runtime Error

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

used_list = []
num = 0

def DFS(i,used_list,num):
    if i == N:
        num += 1
        return num

    s = S[i]
    # S[i]を使わない場合
    num = DFS(i+1,used_list,num)

    # S[i]を使う場合
    if s not in used_list:
        used_list.append(s)
        num=DFS(i+1,used_list,num)
        if len(use_list)>0:
            used_list.pop(-1)
    return num
    
       
ans = DFS(0,used_list,num)
print(ans-1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input().rstrip()
maximum = 0

for i in range(n):
    tmp = n
    wari = 1
    for j in range(i):
        tmp *= (n - j - 1)
        wari *= (j + 2)
    tmp = int(tmp/wari)
    maximum += tmp

flag = True
char = []
for i in range(n):
    if s.count(s[i]) > 1:
        flag = False
        char.append(s[i])

if flag:
    print(maximum)
    exit()
elif n == s.count(s[0]):
    print(n)
    exit()

length = len(char)

minus = 0
multi = -(-length//2)
for i in range(int(length/2)):
    minus += n - (i + 1)

print(maximum - multi*minus)

Submission status: Runtime Error

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

l = []

s = ""

def calc(s):
    if len(s) == n:
        s = s.replace(" ", "")
        l.append(s)
        return
    return calc(s + h[len(s)]), calc(s + " ")

calc(s)

print(len(l[:-1]))

Submission status: Runtime Error

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

use_list = []
num = 0

def DFS(i,used_list,num):
    if i == N:
        num += 1
        return num

    s = S[i]
    # S[i]を使わない場合
    num = DFS(i+1,used_list,num)

    # S[i]を使う場合
    if s not in used_list:
        used_list.append(s)
        num=DFS(i+1,used_list,num)
        used_list.pop(-1)

    return num
    
       
ans = DFS(0,use_list,num)
print(ans-1)

Submission status: Runtime Error

Solution code:
n = input()
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: Runtime Error

Solution code:
def calc(hoge):
    if len(hoge) == n:
        hoge = hoge.replace(" ", "")
        l.append(hoge)
        return
    return calc(hoge + h[len(hoge)]), calc(hoge + " ")

n = int(input())
h = list(input())
d = 10 ** 9 - 7
l = []
s = ""
count = 0
calc(s)
l = l[:-1]


for hage in l:
    leng = len(hage)
    hage = set(list(hage))
    if len(hage) == leng:
        count += 1

print(count % d)

Submission status: Runtime Error

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

    flags = dict_gen()
    counts = dict_gen()
    for i in S:
        flags[i] = 1
        counts[i] += 1

    counter = flag_counter(flags)
    print(counter)


def flag_counter(flags):
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    counter = 0
    for i in alphabet:
        counter += flags[i]
    return counter    

def dict_gen():
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    flags = {}
    for i in alphabet:
        flags[i] = 0
    return flags

def check

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

l = []

s = ""

def calc(s):
    if len(s) == n:
        s = s.replace(" ", "")
        l.append(s)
        return
    return calc(s + h[len(s)]), calc(s + " ")

calc(s)

l = l[:-1]

count = 0

for s in l:
    leng = len(s)
    s = set(list(s))
    if len(s) == leng:
        count += 1

d = 10 ** 9 - 7
print(count % d)

Submission status: Runtime Error

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

l = []

s = ""

def calc(s):
    if len(s) == n:
        s = s.replace(" ", "")
        l.append(s)
        return
    return calc(s + h[len(s)]), calc(s + " ")

calc(s)

l = l[:-1]

count = 0

for s in l:
    leng = len(s)
    s = set(s)
    if len(s) == leng:
        count += 1

d = 10 ** 9 - 7
print(count % d)

Submission status: Runtime Error

Solution code:
print(NO)

Submission status: Runtime Error

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

l = []

s = ""

def calc(s):
    if len(s) == n:
        s = s.replace(" ", "")
        l.append(s)
        return
    return calc(s + h[len(s)]), calc(s + " ")

calc(s)

count = 0

for s in l:
    leng = len(s)
    s = set(s)
    if len(s) == leng:
        count += 1
    else:
        continue

d = 10 ** 9 - 7
print(int((count-1) % d))

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N = I()
s = S()

inf = 10**9+7

from math import factorial
def c(n, r):
    a = factorial(n) / factorial(r) / factorial(n - r)
    return a

result = 0
counts = collections.Counter(s)
red = [i for i in counts.values()]
tmp = 1
for i in red:
    tmp *= i
#  print('tmp', tmp)
for i in range(1, len(s)+1):
    #  print(i)
    #  import pdb
    #  pdb.set_trace()
    #  combis = list(itertools.combinations(counts, i))
    #  print('combis' ,combis)
    result += c(len(s), i)
    #  for combi in combis:
    #      #  print('combi', combi)
    #      tmp = 1
    #      for c in combi:
    #          #  print('c', c)
    #          tmp *= counts[c]
    #      #  print('tmp', tmp)
    #      result += tmp
if tmp != 1:
    for i in range(1, tmp):
        if tmp < i:
            result -= c(tmp, i)
print(int(result)%inf)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input().rstrip()
maximum = 0

for i in range(n):
    tmp = n
    wari = 1
    for j in range(i):
        tmp *= (n - j - 1)
        wari *= (j + 2)
    tmp = int(tmp/wari)
    maximum += tmp

flag = True
char = []
for i in range(n):
    if s.count(s[i]) > 1:
        flag = False
        char.append(s[i])

if flag:
    print(maximum)
    exit()

length = len(char)

minus = 0
multi = -(-length//2)
for i in range(int(length/2)):
    minus += n - (i + 1)

print(maximum - multi*minus)

Submission status: Runtime Error

Solution code:
import itertools

def is_uniqe(x):
    return len(x) == len(set(x))
n = int(input())
s = input()
count = 0
for i in range(n):
    for j in filter(lambda x:is_uniqe(x),itertools.combinations(s,i))
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N = I()
s = S()

inf = 10**9+7

from math import factorial
def c(n, r):
    a = factorial(n) / factorial(r) / factorial(n - r)
    return a

result = 0
counts = collections.Counter(s)
red = [i for i in counts.values()]
tmp = 1
for i in red:
    tmp *= i
#  print('tmp', tmp)
for i in range(1, len(s)+1):
    #  print(i)
    #  import pdb
    #  pdb.set_trace()
    #  combis = list(itertools.combinations(counts, i))
    #  print('combis' ,combis)
    result += c(len(s), i)
    #  for combi in combis:
    #      #  print('combi', combi)
    #      tmp = 1
    #      for c in combi:
    #          #  print('c', c)
    #          tmp *= counts[c]
    #      #  print('tmp', tmp)
    #      result += tmp
if tmp != 1:
    for i in range(1, tmp):
        result -= c(tmp, i)
print(int(result)%inf)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)
N = int(input())
C = [int(input())]
cindex = {C[0]:[0]}
mod = 7 + 10 ** 9
counter = 0
for _ in range(N-1):
    c = int(input())
    if c != C[-1]:
        C.append(c)
        counter += 1
        if c in cindex:
            cindex[c].append(counter)
        else:
            cindex[c] = [counter]

def variation(i, memo = {}):
    if i == len(C)-1: return 1
    try:
        return memo[i]
    except KeyError:
        total = 0
        L = cindex[C[i]]
        for l in L:
            if l > i:
                total += variation(l, memo) #lまで塗る
                total %= mod
                break
        total += variation(i + 1, memo)
        total %= mod
        memo[i] = total
        return total
 
memo = {}
print(variation(0, memo))

Submission status: Runtime Error

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

l = []

s = ""

def calc(s):
    if len(s) == n:
        s = s.replace(" ", "")
        l.append(s)
        return
    return calc(s + h[len(s)]), calc(s + " ")

calc(s)

count = 0

for s in l:
    leng = len(s)
    s = set(s)
    if len(s) == leng:
        count += 1
    else:
        continue

print(count)

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N = I()
s = S()

inf = 10**9+7

from math import factorial
def c(n, r):
    a = factorial(n) / factorial(r) / factorial(n - r)
    return a

result = 0
counts = collections.Counter(s)
red = [i for i in counts.values()]
tmp = 1
for i in red:
    tmp *= i
#  print('tmp', tmp)
for i in range(1, len(s)+1):
    #  print(i)
    #  import pdb
    #  pdb.set_trace()
    #  combis = list(itertools.combinations(counts, i))
    #  print('combis' ,combis)
    result += c(len(s), i)
    #  for combi in combis:
    #      #  print('combi', combi)
    #      tmp = 1
    #      for c in combi:
    #          #  print('c', c)
    #          tmp *= counts[c]
    #      #  print('tmp', tmp)
    #      result += tmp
for i in range(1, tmp):
    result -= c(tmp, i)
print(int(result)%inf)

Submission status: Runtime Error

Solution code:
from itertools import combinations
N = int(input())
S = input()
a = 10**9 + 7
ans = sum([len([1 for t in combinations(S, i) if len(t)==len(set(t))]) for i in range(1, nunique+1)])
print(ans % a)

Submission status: Runtime Error

Solution code:
from collections import Counter
import numpy as np
n = int(input())
s = input()

counter = Counter(s)
counts = 0
vals = np.array(list(counter.values()))
counts = np.prod(vals + 1) - 1
print(int(counts) % (1e9 + 7)))

Submission status: Runtime Error

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

l = []

s = ""

def calc(s):
    if len(s) == n:
        s = s.replace(" ", "")
        l.append(s)
        return
    return calc(s + h[len(s)]), calc(s + " ")

calc(s)

count = 0

for s in l:
    leng = len(s)
    s = set(s)
    if len(s) == leng:
        count += 1

d = 10 ** 9 - 7

print((count-1) % d)

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
h = list(input())

l = []

s = ""

def calc(s):
    if len(s) == n:
        s = s.replace(" ", "")
        l.append(s)
        return
    return calc(s + h[len(s)]), calc(s + " ")

calc(s)

count = 0

for s in l:
    leng = len(s)
    s = set(s)
    if len(s) == leng:
        count += 1

d = 10 ** 9 - 7

print((count-1) % d)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

def cal(n, S):
    if n == 1:
        return sum(S)
    ans = 0
    if n == 2:
        for i in range(len(S) - 1):
            for j in range(i+1, len(S)):
                ans += S[i] * S[j]
    else:
        for i in range(len(S) - n + 1):
            cross = cal(n-1, S[i+1:])
            cross %= 10 ** 9 + 7
            ans += S[i] * cross
            ans %= 10 ** 9 +7
        return ans % 10 ** 9 + 7

ans = 0
for i in range(n):
    ans += cal(i+1, S)

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

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N = I()
s = S()

inf = 10**9+7

from math import factorial
def c(n, r):
    a = factorial(n) / factorial(r) / factorial(n - r)
    return a

result = 0
counts = collections.Counter(s)
red = [i for i in counts.values() if i != 1]
tmp = 1
for i in red:
    tmp *= i
#  print('tmp', tmp)
for i in range(1, len(s)+1):
    #  print(i)
    #  import pdb
    #  pdb.set_trace()
    #  combis = list(itertools.combinations(counts, i))
    #  print('combis' ,combis)
    result += c(len(s), i)
    #  for combi in combis:
    #      #  print('combi', combi)
    #      tmp = 1
    #      for c in combi:
    #          #  print('c', c)
    #          tmp *= counts[c]
    #      #  print('tmp', tmp)
    #      result += tmp
for i in range(1, tmp):
    result -= c(tmp, i)
print(int(result)%inf)

Submission status: Runtime Error

Solution code:
import math
import copy
 
 
 
 
def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:
 
            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l
 

n=input()
s=input()

mod=1000000007
def help1(a):
    all=0
    a1=1
    a2=1
    
    b1=1
    while a!=0:
        a1=a1*a
        a2=a2*b1
        b1+=1
        tmp=(int)(a1/a2)
        a=a-1
        all=(all+tmp)%mod
    return all

def func():
    count=help1(len(s))
    dic={}

    for c in s:
        if c in dic:
            dic[c]=dic[c]+1
        else:
            dic[c]=1
    res=len(s)
    l=[]
    for k in dic:
        if dic[k]==1:
            l.append(k)
    for obj in l:
        del dic[obj]
        
    count2=1
    sum1=0
    for k in dic:
        sum1+=dic[k]
        count2=count2*(1+dic[k])



    number3=help1(sum1)-count2+1

    number4=help1(len(s)-sum1)+1

    number3=number3*number4
    return count-number3
  

print(func())

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N = I()
s = S()

inf = 10**9+7

from math import factorial
def c(n, r):
    a = factorial(n) / factorial(r) / factorial(n - r)
    return a

result = 0
counts = collections.Counter(s)
red = [i for i in counts.values() if i != 1]
tmp = 1
for i in red:
    tmp *= i
#  print('tmp', tmp)
chars = list(set(s))
for i in range(1, len(s)+1):
    #  print(i)
    #  import pdb
    #  pdb.set_trace()
    #  combis = list(itertools.combinations(chars, i))
    #  combis = list(itertools.combinations(counts, i))
    #  print('combis' ,combis)
    result += c(len(s), i)
    #  for combi in combis:
    #      #  print('combi', combi)
    #      tmp = 1
    #      for c in combi:
    #          #  print('c', c)
    #          tmp *= counts[c]
    #      #  print('tmp', tmp)
    #      result += tmp
for i in range(1, tmp):
    result -= c(tmp, i)
print(int(result))

Submission status: Runtime Error

Solution code:
n = int(input())

M = pow(10, 9) + 7
import sys

dc = {}
al = [0]

rr = [1]


def search(ss, start, end):
    z = al[(start + end)//2]
    nz = al[(start + end)//2+1]
    if z <= ss and ss < nz:
        return (start+end)//2
    elif ss < z:
        return search(ss, start, (start+end)//2)
    else:
        return search(ss, (start+end)//2+1, end)

c = 0
cn = 0
for line in sys.stdin:
    a = int(line)
    if a in dc:
        ss = dc[a]
        if ss != c-1:
            if ss >= al[cn]:
                rr.append((rr[cn]*2)%M)
            else:
                i = search(ss, 0, cn)
                rr.append((rr[cn] + rr[i])%M)
            al.append(c)
            cn += 1
    dc[a] = c
    c += 1
print(rr[cn]%M)

Submission status: Runtime Error

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
S = str(input())
l = []
count = 0
for j in S:
    l.append(j)
l_unique = list(set(l))
for k in l_unique:
    c = l.count(k)
    if c > 1:
        count += 1
if count <= 1:
    ans = s - s_a
else:
    s = 0
    s_a = 0
    for i in range(N):
        s += combinations_count(N, i+1)
    for m in range(N-count+1):
        s_a += combinations_count(N-count, m) * count
    add = (N-3) * combinations_count(count, 2)
    ans = s - s_a + add

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

Submission status: Runtime Error

Solution code:
import copy
inputs = [input() for i in range(2)]
n = int(inputs[0])
s = inputs[1]
count = 0
m = 10 ** 9 + 7


def func(i, l):
    if s[i] not in l:
        global count
        count = (count+1) % m
        if i+1 < n:
            func(i+1, l)
            l2 = copy.deepcopy(l)
            l2.append(s[i])
            func(i+1, l2)
    else:
        if i+1 < n:
            func(i+1, l)


l = []
func(0, l)
print(count)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input().rstrip()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s:
        eng_dict[i] += 1
    ans = 1
    size = 10**9+7
    for i in eng_dict.values():
        ans = (ans*i)%size
    print((ans-1)%size)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input().rstrip()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s:
        eng_dict[i] += 1
    ans = 1
    size = 10**9+7
    for j in eng_dict.values():
        ans = (ans*j)%size
    print(ans-1)

Submission status: Runtime Error

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

  count = N
  combination = [list(map(set, list(itertools.combinations(S, n + 1)))) for n in range(1, N)]
  for n in range(1, N):
    comb = combination[n - 1]  # 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))


if __name__ == "__main__":
  foo()

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

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

kind = set(S)
each_char =[]

for char in kind:
    each_char.append(S.count(char))

length = len(kind)
over_stock = len(S) - len(kind)

count = 0
for i in range(over_stock + 1):
    count += (2 ** (length - i)) * comb(over_stock, i, exact=True) % (10 ** 9 + 7)

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

Submission status: Runtime Error

Solution code:
import itertoos


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

count = N
combination = [list(map(set, list(itertools.combinations(S, n + 1)))) for n in range(1, N)]
for n in range(1, N):
  comb = combination[n - 1]  # 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: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input())
    s = input().rstrip()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s:
        eng_dict[i] += 1
    ans = 1
    for i in eng_dict.values():
        ans = (ans*i)%(10**9+7)
    print(ans-1)

Submission status: Runtime Error

Solution code:
import itertoos

def foo():
  N = int(input())
  S = input()

  count = N
  combination = [list(map(set, list(itertools.combinations(S, n + 1)))) for n in range(1, N)]
  for n in range(1, N):
    comb = combination[n - 1]  # 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))


if __name__ == "__main__":
  foo()

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input().rstrip()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s:
        eng_dict[i] += 1
    ans = 1
    for i in eng_dict.values():
        ans = (ans*i)%(10**9+7)
    print(ans-1)

Submission status: Runtime Error

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

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: Runtime Error

Solution code:
N, A, B = map(int,input().split())
print("NO")

Submission status: Runtime Error

Solution code:
count = 0

N = int(input())
S = input()
for j in range(1,N+1):
    for string in itertools.combinations(S, r = j):
        if len(set(string)) == len(string):
            print(string)
            count += 1


print(count)

Submission status: Runtime Error

Solution code:
l = int(input())
s = input()
s_dict = {}
for i in range(0, len(s)):
    if not s[i] in s_dict:
        s_dict[s[i]] = 1
    else:
        s_dict[s[i]] += 1
ans = 2**l
for v in s_dict.values():
    if not v == 1:
        ans *= (v+1)/2**v

print(int(ans-1)%(10**9+7))