Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def reachable_by_3steps_from(node, edges):
    dist1 = edges[node]
    dist2 = []
    for d1 in dist1:
        dist2 += edges[d1]
    reachable = []
    for d2 in dist2:
        reachable += edges[d2]
    return reachable


n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    _from, to = map(int, input().split())
    edges[_from-1].append(to-1)

start, goal = map(int, input().split())
skip_path = [[] for _ in range(n)]
for i in range(n):
    skip_path[i] = reachable_by_3steps_from(i, edges)

todo = deque([])
seen = [False] * n
seen[start-1] = True
for to in skip_path[start-1]:
    todo.append([to, 1])
    if to == goal-1:
        print(1)
        exit()

while todo:
    node, dist = todo.popleft()
    if seen[node]:
        continue
    seen[node] = True
    for to in skip_path[node]:
        todo.append([to, dist+1])
        if to == goal-1:
            print(dist+1)
            exit()

print(-1)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline


n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    _from, to = map(int, input().split())
    edges[_from-1].append(to-1)

start, goal = map(int, input().split())

todo = deque([])
seen = [[False] * n for i in range(3)]
seen[0][start-1] = True
for to in edges[start-1]:
    dim = 1
    dist = 1
    todo.append([to, dim, dist])

while todo:
    node, dim, dist = todo.popleft()
    if seen[dim][node]:
        continue
    seen[dim][node] = True
    dim += 1
    if dim == 3:
        dim = 0
    for to in edges[node]:
        if seen[dim][to]:
            continue
        todo.append([to, dim, dist+1])
        if to == goal-1 and dim == 0:
            print((dist+1)//3)
            exit()

print(-1)
### BUGGY CODE ###

n,m=map(int,input().split())
MOD=1000000007
a=[]
tmp2=10000000000000
for i in range(m):
    tmp=int(input())
    if (tmp-tmp2)==1:
        print(0)
        exit()
    a.append(tmp)
    tmp2=tmp
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    if i-1 in a:
        dp[i]=dp[i-2]%MOD
    elif i-2 in a:
        dp[i]=dp[i-1]%MOD
    else:
        dp[i]=(dp[i-1]+dp[i-2])%MOD
print(dp[-1])

### FIXED CODE ###

n,m=map(int,input().split())
MOD=10**9+7
dp=[0]*(n+1)
breakstair=[False]*(n+1)
a=[]
for i in range(m):
    tmp=int(input())
    breakstair[tmp]=True
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    if breakstair[i-1]:
        if breakstair[i-2]:
            print(0)
            exit()
        dp[i]=dp[i-2]
    elif breakstair[i-2]:
        dp[i]=dp[i-1]
    else:
        dp[i]=(dp[i-1]+dp[i-2])%MOD
print(dp[-1])
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]
result = 0
for i in range(n):
  s[i] = ''.join(sorted(s[i]))
for i in range(n - 1):
  for j in range(i + 1, n):
    if s[i] == s[j]:
      result += 1
print(result)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
for i in range(n):
  s[i] = ''.join(sorted(s[i]))
t = {}
for i in range(n):
  if s[i] in t:
    t[s[i]] += 1
  else:
    t[s[i]] = 1
print(sum(t[k] * (t[k] -1) // 2 for k in t))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))

b=list(set(a))
c=0
for i in range(len(b)):
    er = a.count( b[i] ) - b[i]
    if er<0:
        er = a.count( b[i] )
    c+=er
print(c)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
counter=Counter(a)
b=list(set(a))
c=0
for i in b:
    k =  counter[i]
    c+= k-i if k-i>=0 else k
print(c)
### BUGGY CODE ###

import numpy as np
N = int(input())
Alist = np.array(list(map(int, input().split())))
while len(Alist) != 1:
    min_index = np.argmin(Alist)
    min_num = Alist[min_index]
    Alist = np.where(Alist % min_num == 0, 0, Alist)
    Alist[min_index] = min_num
    Alist = Alist[Alist.nonzero()]

print(Alist[0])


### FIXED CODE ###

import heapq
N = int(input())
Alist = list(map(int, input().split()))
while len(Alist) > 1:
    heapq.heapify(Alist)
    attack = heapq.heappop(Alist)
    Alist = [a % attack for a in Alist if a % attack != 0]
    heapq.heappush(Alist, attack)
print(Alist[0])
### BUGGY CODE ###

N = int(input())
z = 0
for a in range(N):
    for b in range(N):
        c = N - (a+1)*(b+1)
        if c > 0:
            z = z+1
        else:
            pass
print(z)

### FIXED CODE ###

import math
N = int(input())
z = 0
for a in range(N):
    for b in range(min(a,math.floor(N/(a+1)))):
        if N - (a+1)*(b+1) > 0:
            z = z+2
        else:
            pass
    if N - (a+1)*(a+1) > 0:
        z = z+1
    else:
        pass
print(z)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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()
     

fac = [-1] * (2 * 10**6+1)
inv = [-1] * (2 * 10**6+1)
finv = [-1] * (2 * 10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

initNCMMod(2 * 10**6 + 1)
def main():
    H, W, A, B = LI()
    cnt = 0
    for i in range(H-A):
        way = NCMMod(B + i - 1, i) * NCMMod(W + H - B - i - 2, W - 1 - B)
        way %= mod
        cnt += way
        cnt %= mod
    print(cnt)


main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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()
     

fac = [-1] * (2 * 10**6+1)
inv = [-1] * (2 * 10**6+1)
finv = [-1] * (2 * 10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

initNCMMod(2 * 10**6 + 1)
def main():
    H, W, A, B = LI()
    cnt = 0
    for i in range(H-A):
        way = NCMMod(B + i - 1, i) * NCMMod(W + H - B - i - 2, W - 1 - B)
        way %= mod
        cnt += way
        cnt %= mod
    print(cnt)


main()
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7
# ---------------------------
dp = [0] * (n + 1)
dp[0] = 1
if (1 in a):
    dp[1] = 0
else:
    dp[1] = 1
# dp approach

for i in range(2, n + 1):
    if (i in a):
        dp[i] = 0
    elif (dp[i - 1] == 0 and dp[i - 2] == 0):
        print(0)
        exit()
    else:
        dp[i] = dp[i - 1] + dp[i - 2]


print(dp[n] % MOD)


### FIXED CODE ###

n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
'''
a = [0] * (10 ** 5)
for i in range(m):
    a[int(input())] = 1
'''

MOD = 10 ** 9 + 7
# ---------------------------
dp = [0] * (n + 1)
dp[0] = 1
if (1 in a):
    # if (a[1] == 1):
    dp[1] = 0
else:
    dp[1] = 1
# dp approach

for i in range(2, n + 1):
    if (i in a):
        # if (a[i] == 1):
        # (x in list)で探索すると、時間がかかるっぽい
        #dp[i] = 0
        continue
    elif (dp[i - 1] == 0 and dp[i - 2] == 0):
        print(0)
        exit()
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


#print(dp[n] % MOD)
print(dp[n])
### BUGGY CODE ###

n = int(input())
S = [int(a) for a in input().split()]
divisor = 10**9 + 7
tot = 0
for i in range(n-1):
  for j in range(i+1,n):
    a = S[i] % divisor
    b = S[j] % divisor
    tot += (a*b % divisor)
    if tot >= divisor:
      tot = tot % divisor
    
print(tot)

### FIXED CODE ###

def multmod(a,b,m):
  ans = 0
  a = a % m
  
  while b:
    if (b & 1): # odd
      ans = (ans + a) % m
    
    a = (2 * a) % m
    b >>= 1 # b = b / 2
    
  return ans

n = int(input())
S = [int(a) for a in input().split()]
divisor = 10**9 + 7
tot = 0
a,b = 0,0
arr_sum = sum(S) #% divisor
arr_ssq = arr_sum*arr_sum #% divisor
isq_sum = 0
for i in range(n):
  isq_sum += S[i]*S[i] #% divisor
  
#isq_sum = isq_sum % divisor
tot = (arr_ssq - isq_sum)//2 % divisor

print(tot)
### BUGGY CODE ###

N, M=map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
uf = UnionFind(N)

for _ in range(M):
  A, B  = map(int, input().split())
  uf.union(A-1,B-1)
  
L = list(uf.all_group_members().values())

ans = max( [ len(l) for l in L ] )
print(ans)

### FIXED CODE ###

N, M=map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
    def main(self):
      return max([len(self.members(r)) for r in self.roots()])
uf = UnionFind(N)

for _ in range(M):
  A, B  = map(int, input().split())
  uf.union(A-1,B-1)
  
print(-min(uf.parents))
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
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 _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

ans = []
lines_dict =None
d=None
def main():
    global AB, PX, T
    if 'LOCAL' in os.environ:
        N = 2* 10** 5
        Q = 2 * 10 ** 5
        AB = [[i, i + 1] for i in range(1, N)]
        PX = [[i, 10] for i in range(Q)]
    else:
        N, Q = LI()
        #  AB = []
        T = [[] for _ in range(N+1)]
        PX = [0] * (N+1)
        for i in range(N-1):
            a, b = LI()
            #  AB += (a, b)
            T[a] += [b]
            T[b] += [a]

        for i in range(Q):
            p, x = LI()
            PX[p] += x
        #  perr(AB)
        perr(PX)
        dfs(1, -1)
        for i in PX[1:]:
            print(i, end=' ')
        #  ans = [0 for _ in range(N)]

def dfs(parent, parent_parent):
    perr(PX)
    for node in T[parent]:
        if node != parent_parent:
            perr(node)
            PX[node] += PX[parent]
            dfs(node, parent)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
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 _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

if 'LOCAL' in os.environ:
    N = 2* 10** 5
    Q = 2 * 10 ** 5
    AB = [[i, i + 1] for i in range(1, N)]
    PX = [[i, 10] for i in range(Q)]
else:
    N, Q = LI()
    AB = []
    PX = []
    for i in range(N-1):
        AB.append(LI())

    for i in range(Q):
        PX.append(LI())


"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？

カウントを若い順にやっていく
"""
AB = sorted(AB, key=lambda x: x[0])
perr('AB')
perr(AB)
d = {}
for p, x in PX:
    if p not in d.keys():
        d[p] = 0
    d[p] += x
for a, b in AB:
    if b not in d.keys():
        d[b] = 0
    if a not in d.keys():
        d[a] = 0
    d[b] += d[a]
for i in range(1, N+1):
    print(d[i], end=' ')
### BUGGY CODE ###

def participants_maker(number_of_participates,point):
    return [point]*number_of_participates



def point_getter(participates,respondents):
    for i in range(len(respondents)):
        participates = list(map(lambda x : x-1, participates))
        participates[respondents[i]-1] += 1
    return participates

def discriminate_serviver(result_score):
    result_list = []
    for i in range(len(result_score)):
        if result_score[i] <= 0:
            result_list.append("No")
            print("No")
        else:
            result_list.append("Yes")
            print("Yes")
    return result_list

def main():
    li = list(map(int,input().split()))
    respondents = [int(input()) for i in range(li[2])]
    participates = participants_maker(li[0],li[1])
    result_score = point_getter(participates,respondents)
    discriminate_serviver(result_score)


# if __name__ == "__main__":
#     main()

main()

### FIXED CODE ###

import collections
def main():
    li = list(map(int,input().split()))
    respondents = [int(input()) for i in range(li[2])]
    number_of_respondes = respondes_number_of_participants(respondents)
    check_surviver(number_of_respondes,li[0],li[1],li[2])


def respondes_number_of_participants(respondents):
    return collections.Counter(respondents)


def check_surviver(number_of_respondes,number_of_participants,gived_points,number_of_questions):
    for i in range(number_of_participants):
        if number_of_respondes[i+1]:
            if gived_points - number_of_questions + number_of_respondes[i+1] > 0:
                print("Yes")
            else:
                print("No")
        else:
            if gived_points - number_of_questions > 0:
                print("Yes")
            else:
                print("No")

main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
    x = 0
    for b in A:
        if a%b == 0:
            x += 1
    if x == 1:
        ans += 1
print(ans)
            


### FIXED CODE ###

n = int(input())
a = sorted(map(int, input().split()))
b = [0] * (10 ** 6 + 1)
c = [False] * (10 ** 6 + 1)
for i in a:
    b[i] += 1
ans = 0
for i in range(1, 10 ** 6 + 1):
    if not b[i]:
        continue
    if b[i] == 1 and not c[i]:
        ans += 1
    for j in range(1, 10 ** 6 + 1):
        if i * j > 10 ** 6:
            break
        c[i * j] = True
print(ans)
### BUGGY CODE ###

l, r = map(int, input().split())
ans = []
if r < 2019:
    print((l*(l+1))%2019)
else:
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            ans.append((i*j)%2019)
    print(min(ans))



### FIXED CODE ###

l, r = map(int, input().split())
ans = []
for i in range(l, r+1):
    for j in range(i+1, r+1):
        if j == i+1:
            start = (i*j) % 2019
        tmp = (i*j) % 2019
        if tmp == 0:
            print(0)
            exit()
        if j != i+1 and tmp == start:
            break
        else:
            ans.append(tmp)
print(min(ans))
### BUGGY CODE ###

x,k,d = map(int,input().split())
for i in range(1,k+1):
  if abs(x) >= abs(abs(x) - d):
    x = abs(x) - d
  else:
    if (k-i-1)%2 == 0:
      print(abs(x))
      exit()
    else:
      if abs(x) + d <= abs(abs(x) - d):
        print(abs(x)+d)
        exit()
      else:
        print(abs(abs(x)-d))
        exit()
print(abs(x))


### FIXED CODE ###

x,k,d = map(int,input().split())

if abs(x)//d <= k and k>1000 :
  z = k - (abs(x)//d)
  x = abs(x)%d
  if z % 2 == 0:
    print(x)
    exit()
  else:
    if abs(x) + d <= abs(abs(x) - d):
      print(abs(x)+d)
      exit()
    else:
      print(abs(abs(x)-d))
      exit()
elif abs(x)//d > k and k>1000 :
  x = abs(x) - k*d
  print(abs(x))
  exit()
else:
  for i in range(1,k+1):
    if abs(x) >= abs(abs(x) - d):
      x = abs(x) - d
    else:
      if (k-i-1)%2 == 0:
        print(abs(x))
        exit()
      else:
        if abs(x) + d <= abs(abs(x) - d):
          print(abs(x)+d)
          exit()
        else:
          print(abs(abs(x)-d))
          exit()
print(abs(x))
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
H, W = list(map(int, input().split()))
L = [[j for j in input()] for i in range(H)]
blacks = [[i, j] for i in range(H) for j in range(W) if L[i][j] == "#"]
black_count = len(blacks)

cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
all_count = H * W
result = 0
while black_count < all_count:
  next_blacks = []
  for black in blacks:
    for cand in cands:
      i = black[0] + cand[0]
      j = black[1] + cand[1]
      if i >= 0 and i < H and j >= 0 and j < W:
        if L[i][j] == ".":
          L[i][j] = "#"
          next_blacks.append([i, j])
  black_count += len(next_blacks)
  blacks = next_blacks
  result += 1

print(result)


### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
from string import ascii_lowercase
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
S = read_str()

res = 1
count = [0 for _ in range(26)]
alpha = ascii_lowercase

for i in range(N):
    if S[i] in S[:i]:
        count[alpha.find(S[i])] = S[:i].count(S[i]) + 1
        res += res // count[alpha.find(S[i])]
    else:
        res *= 2
res -= 1
big = 10**9 + 7
print(res % big)


### FIXED CODE ###

import sys
from string import ascii_lowercase
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
S = read_str()

res = 1
count = [0 for _ in range(26)]
alpha = ascii_lowercase

for i in range(N):
    st = alpha.find(S[i])
    count[st] += 1
    if count[st] > 1:
        res += res // count[st]
    else:
        res *= 2
res -= 1
big = 10**9 + 7
print(res % big)
### BUGGY CODE ###

from collections import deque

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    matrix = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        matrix[i][i] = 0
    for s in range(N):
        d = deque([s])
        while(len(d) > 0):
            v = d.popleft()
            if v == X:
                if matrix[s][Y] == -1:
                    d.append(Y)
                    matrix[s][Y] = matrix[s][v] + 1
            if v == Y:
                if matrix[s][X] == -1:
                    d.append(X)
                    matrix[s][X] = matrix[s][v] + 1
            if v + 1 < N:
                if matrix[s][v+1] == -1:
                    d.append(v+1)
                    matrix[s][v+1] = matrix[s][v] + 1
            if v - 1 >= 0:
                if matrix[s][v-1] == -1:
                    d.append(v-1)
                    matrix[s][v-1] = matrix[s][v] + 1
    
    cnt = {k: 0 for k in range(1, N)}
    for h in range(N):
        for w in range(h+1, N):
            cnt[matrix[h][w]] += 1
    
    for k in range(1, N):
        print(cnt[k])


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    ans = [0 for _ in range(N)]
    for s in range(N):
        dist = [-1 for _ in range(N)]
        dist[s] = 0

        d = deque([s])
        while(len(d) > 0):
            v = d.popleft()
            if v == X:
                if dist[Y] == -1:
                    d.append(Y)
                    dist[Y] = dist[v] + 1
            if v == Y:
                if dist[X] == -1:
                    d.append(X)
                    dist[X] = dist[v] + 1
            if v + 1 < N:
                if dist[v+1] == -1:
                    d.append(v+1)
                    dist[v+1] = dist[v] + 1
            if v - 1 >= 0:
                if dist[v-1] == -1:
                    d.append(v-1)
                    dist[v-1] = dist[v] + 1

        for i in range(N):
            ans[dist[i]] += 1
  
    for k in range(1, N):
        print(ans[k] // 2)


if __name__ == "__main__":
    main()