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:
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:
import math

mod = 10**9 + 7

n = int(raw_input())
s = raw_input()

def comb(r,n):
  if r == 0: return 1
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0

q = []

for a in "abcdefghijklmnopqrstuvwxyz":
  q.append( s.count(a) )

#print q

for a in range(1,min(26+1,n+1)):
  ans += comb(a,n)

  for b in range(len(q)):
    if q[b] > 1 and a > 1:
      #print a,q[b]
      #print comb(2,q[b]) * comb(a-2,n-q[b])
      ans -= comb(2,q[b]) * comb(a-2,n-q[b])
      for c in range(b+1,len(q)):
        if q[c] > 1 and a > 3:
          ans += comb(2,q[b]) * comb(2,q[c]) * comb(a-2-2,n-q[b]-q[c])

print ans % mod

Submission status: Runtime Error

Solution code:
import math

  str = input()
  l = len(list(set(list(str))))
  print( math.factorial(l + 1) % (pow( 10, 9 ) + 7 ))

Submission status: Runtime Error

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
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)):
        N = N + reduce(mul, com[k])

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

Submission status: Runtime Error

Solution code:
import math
  
l = len(list(set(list(input()))))


      print( math.factorial(l + 1) % (pow( 10, 9 ) + 7 ))

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)

print(count - 1)

Submission status: Runtime Error

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+=sum(kumiawase)
print(answer%(7+10**9))

Submission status: Runtime Error

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

Submission status: Runtime Error

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+=sum(kumiawase)
print(answer)

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 =ans* (1-1/2**v)

print(int(ans-1))

Submission status: Runtime Error

Solution code:
N = input()
s = input()
hoge = []
charlist = list(s)
result = 1
Alist = ["q","w","e","r","t","y","u","i","o","p","a","s","d","f","g","h","j","k","l","z","x","c","v","b","n","m"]
for i in Alist:
    hoge.append(charlist.count(i))
for j in hoge:
    result = result * (j + 1)
print((result -1) ¥ (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
from sys import stdin

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:
from scipy.special 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)

print(count - 1)

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 =ans* (1-1/2**v)

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

Submission status: Runtime Error

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

Solution code:
#coding: utf-8
import math

def main():
    line_input = input()
    line_split = line_input.split()
    A = int(line_split[0])
    B = int(line_split[1])
    C = int(line_split[2])
    max_num = math.floor(B / A)
    if max_num > C:
        print(C)
    else:
        print(max_num)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

MOD = 1e9 + 7
L = {}
for i in S:
  if i in L:
    L[i] += 1
  else:
    L[i] = 1

Ans = 1
for i in range(N):
  Ans = (Ans * 2) % MOD
Ans -= 1

t = 0
k = 1
for i in L.values():
  N -= i
  if i != 1:
    t += (k * (2 ** N) * ((2 ** i) - (i + 1))) % MOD
  k *= i + 1

Ans -= t

print(int(Ans % MOD))

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 *= ((2**v-1)/2**v)

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

Submission status: Runtime Error

Solution code:
def kaizyo(n):
        if n == 0:
                return 1
        else:
                return n * kaizyo(n-1)

N = int(input())
S = input()
ans = 0
for i in range(1,N+1):
        print(i)
        ans += (kaizyo(N)//kaizyo(N-i))//kaizyo(i)
dif = 0



print(ans)

Submission status: Runtime Error

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

MOD = 1e9 + 7
L = {}
for i in S:
  if i in L:
    L[i] += 1
  else:
    L[i] = 1

Ans = (2 ** N - 1) % MOD
t = 0
k = 1
for i in L.values():
  N -= i
  if i != 1:
    t += (k * (2 ** N) * ((2 ** i) - (i + 1))) % MOD
  k *= i + 1

Ans -= t % MOD

print(int(Ans % MOD))

Submission status: Runtime Error

Solution code:
import string

n=int(input())
s=ss=input()
ans=n**2

abc=string.ascii_lowercase
for i in range(26):
    if 1<s.count(abc[i]):
        ss=ss.replace(abc[i],"")
        ans1=ans-(ans-len(ss)**2)/2
        break        
print(int(ans1))

Submission status: Runtime Error

Solution code:
import string

n=int(input())
s=ss=input()
ans=n**2

abc=string.ascii_lowercase
for i in range(26):
    if 1<s.count(abc[i]):
        ss=ss.replace(abc[i],"")
        ans1=ans-(ans-len(ss)**2)/2
	break        
print(int(ans1))

Submission status: Runtime Error

Solution code:
import math

def create_gen(string):
    for char in string:
        yield char
        
  str = input()
  origin_list = list(create_gen(str))
  for i, _ in enumerate(origin_list, 1):
      i = len(itertools.combinations(origin_list, r=i))
      print( i % (pow( 10, 9 ) + 7 ))

Submission status: Runtime Error

Solution code:
import itertools

N = int(input())
S = [s for s in input()]
ans = 0
for n in range(1,N+1):
    a = list(itertools.combinations(S,min(n,(N-n)))
    a = [i for i in a if len(i) == len(set(i))]
    ans += len(a)
    
print(ans%(10**9 + 7))

Submission status: Runtime Error

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

MOD = 1e9 + 7
L = {}
for i in S:
  if i in L:
    L[i] += 1
  else:
    L[i] = 1

Ans = (2 ** N - 1) % MOD
t = 0
k = 1
for i in L.values():
  N -= i
  if i != 1:
    t += (k * (2 ** N)) % MOD
  k *= i + 1

Ans -= t % MOD

print(int(Ans % MOD))

Submission status: Runtime Error

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

MOD = 1e9 + 7
L = {}
for i in S:
  if i in L:
    L[i] += 1
  else:
    L[i] = 1

Ans = (2 ** N - 1) % MOD
t = 0
k = 1
for i in L.values():
  N -= i
  if i != 1:
    t += k * (2 ** N)
  k *= i + 1

Ans -= t

print(int(Ans % MOD))

Submission status: Runtime Error

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

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

MOD = 1e9 + 7
L = {}
for i in S:
  if i in L:
    L[i] += 1
  else:
    L[i] = 1

Ans = 2 ** N - 1
t = 0
k = 1
for i in L.values():
  N -= i
  if i != 1:
    t += k * (2 ** N)
  k *= i + 1

Ans -= t

print(int(Ans % MOD))

Submission status: Runtime Error

Solution code:
import collections
n=int(input())
S=input()
c=collections.Counter(S)
C=len(c)
ans=2**C*1.5**(n-C)
ans-=1
ans%=(10**9+7)
print(int(ans))

Submission status: Runtime Error

Solution code:
def a(s: str, nokori: str) -> int:
    if (sorted(list(s)) == sorted(list(set(s)))):
        if(len(nokori)==0):
            return 1
        else:
            return a(s, nokori[1:]) + a(s+nokori[0], nokori[1:])
    else:
        return 0


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

sum = 0
if(len(s)>0):
    sum = a("", s[1:]) + a(s[0], s[1:])
    print((sum-1)%1000000007)
else:
    print(0)

Submission status: Runtime Error

Solution code:
n=int(input())
s=list(map(int,input().split()))
ans=0
z=list(set(s))
m=len(z)
for i in range(m):
    ans+=s.count(z[i])*(2**(m-1))
print(ans-m+1)

Submission status: Runtime Error

Solution code:
def bubunCnt(s):
    memo={}
    memo_already={}
    cnt = bubun_cnt(s, memo, memo_already)
    return cnt

def bubun_cnt(s, memo, memo_already):
    if s in memo_already.keys():
        return 0
    
    if len(s)==0:
        return 0
    
    if len(s)==1:
        memo[s] = 1
        memo_already[s]=True
        return 1
    
    # has memory
    if s in memo.keys():
        return memo[s]
    
    ret = 1
    for i in range(len(s)):
        new_s = s[:i]+s[i+1:]
        ret += bubun_cnt(new_s, memo, memo_already)
    
    memo[s] = ret
    memo_already[s]=True
    return ret
  

n = int(input())
s = input()
print(bubunCnt(s))

Submission status: Runtime Error

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

 
numdiff = bin(A ^ B).count("1")
if numdiff >= 2 ** N:
    print("NO")

elif numdiff % 2 == 0:
    print("NO")
    
else:
    print("YES")
    ct = 0
    lt = list(bin(A)[2:])
    fb = list(bin(B)[2:])
    if lt == []:
        lt.append("0")
    print(A, end = " ")
    
    while ct < 2 ** N - 2:
        if len(lt) < len(fb):
            lt = ["0"] * (len(fb) - len(lt)) + lt
        else:
            fb = ["0"] * (len(lt) - len(fb)) + fb
        if lt == fb:
            if lt[0] == "0":
                lt[0] = "1"
            else:
                lt[0] = "0"
            print(int("".join(lt), 2), end = " ")
        else:
            for i in range(len(lt)):
                if lt[i] == "1" and fb[i] == "0":
                    lt[i] = "0"
                    print(int("".join(lt), 2), end = " ")
                    break
                if lt[i] == "0" and fb[i] == "1":
                    lt[i] = "1"
                    print(int("".join(lt), 2), end = " ")
                    break
        ct += 1
    print(B, end = " ")

Submission status: Runtime Error

Solution code:
import itertools

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

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

long long N, ans, M, cnt[26];
char S;

int main() {
  M = 1e9 + 7;
  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> S;
    cnt[S - 'a']++;
  }

  ans = 1;
  for (int i = 0; i < 26; i++) {
    ans *= (cnt[i] + 1);
    ans %= M;
  }

  cout << ans - 1 << '\n';

  return 0;
}

Submission status: Runtime Error

Solution code:
mod = 1000000007
n = int(input())
s = input()
abets = “abcdefghijklmnopqrstuvwxyz”
counts = []
for c in abets:
  counts.append(s.count(c))
ans = 0
for ptn in range(2** len(abets)):
  bin_str = format(ptn, ‘b’)
  subans = 1
  for i, b in enumerate(bin_str[::-1]):
    if b == ‘1’:
      subans = (subans * counts[i]) % mod
  ans = (ans + subans) % mod
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import itertools


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

def count_up(s_count):
  strings = list(s_count.keys())
  ans = 0
  for num in range(1, len(strings) + 1):
    for s_list in itertools.combinations(strings, num):
      num_list = [s_count[s] for s in s_list]
      ans += reduce((lambda x, y: x * y), num_list)
  print(ans % (10**9 + 7))

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

s_count = analyze(string)
count_up(s_count)

Submission status: Runtime Error

Solution code:
import itertools

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

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

Submission status: Runtime Error

Solution code:
input()
S = input().strip()
type = len(set(list(S)))

def DP(i,s):
  me = 1 if len(s) > 0 else 0
  # 葉
  if len(S) <= i:
    return me
  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: Runtime Error

Solution code:
#include <iostream>
#include <map>

unsigned long hoge(const std::map<char, unsigned int>& alphabet_map, unsigned int x) {
  for  i in [(), (), ()]:
  
}

int main() {
  unsigned int n;
  std::string s;
  std::cin >> n;
  std::cin >> s;

  std::map<char, unsigned int> alphabet_map;
  for (unsigned int i = 0; i < n; ++i) {
    alphabet_map[s[i]] += 1;
  }

  for (const auto x : alphabet_map) {
    std::cout << x.first << ": " << x.second << std::endl;
  }
  std::cout << alphabet_map.size() << std::endl;

  unsigned long sum = 0;
  for (unsigned int i = 1; i <= alphabet_map.size(); ++i) {
    sum += hoge(i);
  }

  return sum % (1000000000 + 7);
}

Submission status: Runtime Error

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

"""
S=""
import random
AL=["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"]
for i in range(10):
    t=int(random.random()*20)
    S+=AL[t]
    print(AL[t])
    print(S)
print(S)
"""
obj={}
L=[]
r=1
for i in S:
    if i in L:
        obj[S[i]]+=1
        r=r*(1+1/(2**obj[i]))
    else:
        r*=2
        obj[i]=0
        L.append(i)

    if r>(10**9+7):
        r-=(10**9+7)
        
print(r-1)

Submission status: Runtime Error

Solution code:
n=int(input())
S=input()
a='abcdefghijklmnopqrstuvwxyz'
ans=1
for i in range(26):
  cnt=S.count(a[i])
  if cnt >0:
    ans=ans*(1.5**(cnt-1))*2
ans-=1
ans=ans%(10**9+7)
print(int(ans))

Submission status: Runtime Error

Solution code:
input()
S = input().strip()
color = len(set(list(S)))

def DP(i,s):
  me = 1 if len(s) > 0 else 0
  # 葉
  if len(S) <= i:
    return 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: Runtime Error

Solution code:
n=int(input())
S=input()
a='abcdefghijklmnopqrstuvwxyz'
ans=1
for i in range(26):
  cnt=S.count(a[i])
  if cnt >0:
    ans=ans*(1.5**(cnt-1))*2
ans=ans%(10**9+7)
ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
def a(s: str, nokori: str) -> int:
    if(len(nokori)==0):
        if(sorted(list(s))==sorted(list(set(s)))):
            return 1
        else:
            return 0
    else:
        return a(s, nokori[1:]) + a(s+nokori[0], nokori[1:])

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

sum = 0
if(len(s)>0):
    sum = a("", s[1:]) + a(s[0], s[1:])
    print((sum-1)%1000000007)
else:
    print(0)

Submission status: Runtime Error

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

    n = int(input())
    s = input()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s[:-1]:
        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:
N = int(input())
S =list(input())
s = list(set(S))
m = 1
for i in range(len(s)):
    m *= (S.count(s[i]) + 1)
    
print((m - 1) % (10 ** 9 + 7)

Submission status: Runtime Error

Solution code:
n=int(input())
S=input()
a='abcdefghijklmnopqrstuvwxyz'
ans=1
for i in range(26):
  cnt=S.count(a[i])
  if cnt >0:
    ans=ans*(1.5**(cnt-1))*2
  ans=ans%(10^9+7)
ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
def a(s: str, nokori: str) -> int:
    if(len(nokori)==0):
        if(sorted(list(s))==sorted(list(set(s)))):
            return 1
        else:
            return 0
    else:
        return a(s, nokori[1:]) + a(s+nokori[0], nokori[1:])

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

sum = 0

sum = a("", s[1:]) + a(s[0], s[1:])

print(sum-1)

Submission status: Runtime Error

Solution code:
n=int(input())
S=input()
a='abcdefghijklmnopqrstuvwxyz'
ans=1
for i in range(26):
  cnt=S.count(a[i])
  if cnt >0:
    ans=ans*(1.5**(cnt-1))*2
    ans=ans%(10^9+7)
ans-=1
print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100005)
_=int(input())
s=input()
mod=7+10**9
def dp(t,l):
    if len(t)==1:
        if t[0] in l:
            return 1
        else:
            return 2
    if t[0] in l:
        return dp(t[1:],l)%mod
    else:
        g=l+[t[0]]
        ans=dp(t[1:],g)+dp(t[1:],l)
        ans%=mod
        return ans

print(dp(s,[])-1)

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
    for k in dic:
        if dic[k]>1:

            count=(count+mod-(help1(dic[k])+mod-dic[k])*help1(len(s)-dic[k])%mod)%mod
    return count
  

print(func())

Submission status: Runtime Error

Solution code:
N = int(input())
S = input().strip()
S += "aaaa"

def tree(N,s,index):
  if N <= index:
      if len(s) > 0:
          return 1
      else:
          return 0

  if S[index] in s:
      return tree(N,s, index + 1)
  else:
      return tree(N,s, index + 1) + tree(N,s + S[index], index + 1)


print(tree(N,"",0) % 1000000007)

Submission status: Runtime Error

Solution code:
_=input()
s=input().rstrip()
mod=7+10**9
def dp(t,l):
    if len(t)==1:
        if t[0] in l:
            return 1
        else:
            return 2
    elif t[0] in l:
        return dp(t[1:],l)%mod
    else:
        g=l+[t[0]]
        ans=dp(t[1:],g)+dp(t[1:],l)
        ans%=mod
        return ans
print(dp(s,[])-1)

Submission status: Runtime Error

Solution code:
import sys
from  collections import deque
sys.setrecursionlimit(10^7)
def dfs(base, n, s, cur):
  if cur == n:
    return 1
  else:
    return (dfs(base, n, s, cur+1)+(0 if base[cur] in s else dfs(base, n, s+base[cur], cur+1)))%(10^9+7)

N = int(input())
S = list(input().strip())
print(dfs(S,N,"",0)-1)

Submission status: Runtime Error

Solution code:
n=int(input())
S=input()
a='abcdefghijklmnopqrstuvwxyz'
ans=1
for i in range(26):
  cnt=S.count(a[i])
  if cnt >0:
    ans=ans*(1.5**(cnt-1))*2
ans-=1
ans=ans%(10^9+7)
print(int(ans))

Submission status: Runtime Error

Solution code:
hoge=input()
str=input()

dic={}
for alp in str:
    if alp in dic:
        dic[alp] += 1
    else:
        dic[alp] = 1

ans=1

for alp,num in dic.items():
    ans *= num+1)

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

Submission status: Runtime Error

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

def tree(N,s,index):
  if N <= index:
      if len(s) > 0:
          return 1
      else:
          return 0

  if S[index] in s:
      return tree(N,s, index + 1)
  else:
      return tree(N,s, index + 1) + tree(N,s + S[index], index + 1)


print(tree(N,"",0) % 1000000007)

Submission status: Runtime Error

Solution code:
_=int(input())
s=input()
mod=7+10**9
def dp(t,l):
    if len(t)==1:
        if t[0] in l:
            return 1
        else:
            return 2
    elif t[0] in l:
        return dp(t[1:],l)%mod
    else:
        g=l+[t[0]]
        ans=dp(t[1:],g)+dp(t[1:],l)
        ans%=mod
        return ans
print(dp(s,[])-1)

Submission status: Runtime Error

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

def tree(N,s,index):
  if N <= index:
      if len(s) > 0:
          return 1
      else:
          return 0

  if S[index] in s:
      return tree(N,s, index + 1)
  else:
      return tree(N,s, index + 1) + tree(N,s + S[index], index + 1)


print(tree(N,"",0) % 1000_000_007)

Submission status: Runtime Error

Solution code:
N = int(input())
S = str(input())
dic = {'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}

ans = 1

for i in range(N):
	dic[S[i]] += 1

for key in list(dic.keys()):
	ans *= (dic[key]+1)

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

Submission status: Runtime Error

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

 
numdiff = bin(A ^ B).count("1")

if numdiff >= 2 * N:
    print("NO")

elif N % 2 == 0 and numdiff % 2 == 0:
    print("NO")
    
elif N % 2 == 1 and numdiff % 2 == 1:
    print("NO")
    
else:
    print("YES")
    ct = 0
    lt = list(bin(A)[2:])
    fb = list(bin(B)[2:])
    if lt == []:
        lt.append("0")
    print(A, end = " ")
    
    while ct < N * 2 - 2:
        if len(lt) < len(fb):
            lt = ["0"] * (len(fb) - len(lt)) + lt
        else:
            fb = ["0"] * (len(lt) - len(fb)) + fb
        if lt == fb:
            if lt[0] == "0":
                lt[0] = "1"
            else:
                lt[1] = "0"
            print(int("".join(lt), 2), end = " ")
        else:
            for i in range(len(lt)):
                if lt[i] == "1" and fb[i] == "0":
                    lt[i] = "0"
                    print(int("".join(lt), 2), end = " ")
                    break
                if lt[i] == "0" and fb[i] == "1":
                    lt[i] = "1"
                    print(int("".join(lt), 2), end = " ")
                    break
        ct += 1
    print(B, end = " ")

Submission status: Runtime Error

Solution code:
_=int(input())
s=input()
mod=7+10**9
def dp(t,l):
    if len(t)==1:
        if t[0] in l:
            return 1
        else:
            return 2
    if t[0] in l:
        return dp(t[1:],l)%mod
    else:
        ans=dp(t[1:],l+[t[0]])+dp(t[1:],l)
        ans%=mod
        return ans
print(dp(s,[])-1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
t = "abcdefghijklmnopqrstuvwxyz"
ans = 1

for i in range(n):
    ans *= (s.count(t[i]) + 1)

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import itertools
 

def analyze(string):
  s_count = defaultdict(int)
  for s in string:
    s_count[s] += 1
  return s_count
 
def count_up(s_count):
  strings = list(s_count.keys())
  ans = 0
  for num in range(1, len(strings) + 1):
    for s_list in itertools.product(strings, num):
      a = 1
      for s in s_list:
        a *= s_count[s]
      ans += a
  print(ans)
  
N, string = input().split('\n')
N = int(N)
 
s_count = analyze(string)
count_up(s_count)

Submission status: Runtime Error

Solution code:
import sys
from  collections import deque
sys.setrecursionlimit(10^6)
def dfs(base, n, s, cur):
  if cur == n:
    return 1
  else:
    return (dfs(base, n, s, cur+1)+(0 if base[cur] in s else dfs(base, n, s+base[cur], cur+1)))%(10^9+7)

N = int(input())
S = list(input().strip())
print(dfs(S,N,"",0)-1)

Submission status: Runtime Error

Solution code:
_=int(input())
s=input()
mod=7+10**9
def dp(t,l):
    if len(t)==1:
        if t[0] in l:
            return 1
        else:
            return 2
    if t[0] in l:
        return dp(t[1:],l)
    else:
        return (dp(t[1:],l+[t[0]])+dp(t[1:],l))%mod
print(dp(s,[])-1)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
m = 10**9 + 7
nl = [0 for i in range(26)]
for s in S:
    nl[ord(s)-97] += 1
ans = 1
for i in range(N):
    if nl[i] == 0:
        continue
    else:
        ans *= nl[i] + 1
        ans = ans % m
print(ans-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import itertools


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

def count_up(s_count):
  strings = list(s_count.keys())
  ans = 0
  for num in range(1, len(strings) + 1):
    for s_list in itertools.product(strings, num):
      a = 1
      for s in s_list:
        a *= s_count[s]
      ans += a
  print(ans)
  
N, string = input().split('\n')
N = int(N)

s_count = analyze(string)
count_up(s_count)

Submission status: Runtime Error

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

def tree(N,s,index):
  if N <= index:
      if len(s) > 0:
          return 1
      else:
          return 0

  if S[index] in s:
      return tree(N,s, index + 1)
  else:
      return tree(N,s, index + 1) + tree(N,s + S[index], index + 1)


print(tree(N,"",0))

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
t = "abcdefghijklmnopqrstuvwxyz"
ans = 1

for i in range(n):
    ans *= (s.count(t[i]) + 1)
    if ans > 10**9 + 7:
        ans %= 10**9+7

print(ans-1)