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 sys
#input = sys.stdin.readline
import random
import bisect
import collections
import itertools
import operator
#from statistics import mean, median, variance, stdev




#template input

def IT(): #整数1個
    return int(input())
def IL(): #整数複数
    return [int(_) for _ in input().split()]
def IS(): #文字列複数
    return [_ for _ in input().split()]
def ILS(n): #整数1つ　縦にズラーってなってるやつ
    return [int(input()) for _ in range(n)]
def SLS(n): #文字列　縦にズラーってなってるやつ
    return [input() for _ in range(n)]
def ILSS(n): #整数複数　縦にズラーってなってるやつ
    return [[int(_) for _ in input().split()] for j in range(n)]

#template technique
def bit_full_search(ss):
    n = len(ss)
    for i in range(1 << n):
        s = ""
        for j in range(n + 1):
            if ((1 & i >> j) == 1):
                s += ss[j]
        print(s)
def bit_full_search2(A):
    #https://blog.rossywhite.com/2018/08/06/bit-search/
    value = []
    for i in range(1 << len(A)):
        output = []

        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                #output.append(A[j])
                output.append(A[j])
        value.append([format(i, 'b').zfill(16), sum(output)])

    value.sort(key=lambda x:x[1])
    bin = [value[k][0] for k in range(len(value))]
    val = [value[k][1] for k in range(len(value))]
    return bin, val
def matching_bisect(list1_val, list2_val, n):
    #2分探索
    j = 0
    for i in range(len(list1_val)):
        j = bisect.bisect_left(list2_val, n - list1_val[i])
        if j < len(list2_val):
            if list1_val[i] + list2_val[j] == n:
                #ans = list2_bin[j] + list1_bin[i]
                break
    return j


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def are_same(self, x, y):
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]
















"""ここからメインコード"""


def main():
    n=int(input())
    s=input()
    alp = [0 for i in range(26)]
    for i in range(n):
        alp[ord(s[i])-97] += 1
    ans = 1
    for i in range(n):
        ans *= alp[i]+1


    print(ans-1)





main()

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)

Submission status: Runtime Error

Solution code:
import sys
from  collections import deque
sys.setrecursionlimit(10^5)
memo = deque()
def dfs(base, n, s, cur):
  if cur == n:
    if not s in memo:
      memo.append(s)
      return 1
    else:
      return 0
  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 = list(input())
t = "abcdefghijklmnopqrstuvwxyz"
list = []

for i in range(n):
    list.append(s.count(t[i]))

ans = 1

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

print(ans-1)

Submission status: Runtime Error

Solution code:
import math

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"
list = []

for i in range(n):
    list.append(s.count(t[i]))

ans = 1

for i in range(len(list)):
    ans *= (list[i]+1)
    if ans > 10**9 + 7:
        ans = ans % (10**9+7)

print(ans-1)

Submission status: Runtime Error

Solution code:
_=input()
S=input()
L=[]
r=1
for i in range(len(S)):
    if S[i] in L:
        r=int(r*(3/2))
    else:
        r*=2
        L.append(S[i])

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

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
t = "abcdefghijklmnopqrstuvwxyz"
list = []

for i in range(n):
    list.append(s.count(t[i]))

ans = 1

for i in range(len(list)):
    ans *= (list[i]+1)

print(ans-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
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)