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

N = int(input())
count = 0

for i in range(len(str(N))):
    for j in range(3 * (10**i), 4 * (10**i)):
        if j > N:
            break
        if '0' not in str(j) and '1' not in str(j) and '2' not in str(j) and '4' not in str(j) and '6' not in str(
                j) and '8' not in str(j) and '9' not in str(j) and('7' in str(j) and '5' in str(j) and '3' in str(j)):
            count += 1
    for j in range(5 * (10**i), 6 * (10**i)):
        if j > N:
            break

        if '0' not in str(j) and '1' not in str(j) and '2' not in str(j) and '4' not in str(j) and '6' not in str(
                j) and '8' not in str(j) and '9' not in str(j) and('7' in str(j) and '5' in str(j) and '3' in str(j)):
            count += 1

    for j in range(7 * (10**i), 8 * (10**i)):
        if j > N:
            break
        if '0' not in str(j) and '1' not in str(j) and '2' not in str(j) and '4' not in str(j) and '6' not in str(
                j) and '8' not in str(j) and '9' not in str(j) and('7' in str(j) and '5' in str(j) and '3' in str(j)):
            count += 1
    else:
        continue
    break

print(count)




### FIXED CODE ###

import itertools
N = int(input())
count = 0
for i in range(3, len(str(N)) + 1):
    for j in itertools.product('753', repeat=i):
        if int(''.join(j)) <= N and '3' in str(j) and '5'in str(j) and '7' in str(j):
            count += 1

print(count)
### BUGGY CODE ###

S=input()
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
mod=10**9+7
for i in range(len(S)):
  if(S[i]=='?'):
    for j in range(13):
      for k in range(10):
        l=(j*10+k)%13
        dp[i+1][l]+=dp[i][j]
    for j in range(13):
      dp[i+1][j]%=mod
  else:
    k=int(S[i])
    for j in range(13):
      l=(j*10+k)%13
      dp[i+1][l]+=dp[i][j]
    for j in range(13):
      dp[i+1][j]%=mod
print(dp[len(S)][5])

### FIXED CODE ###

S=input()
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
mod=10**9+7
for i in range(len(S)):
  if(S[i]=='?'):
    for j in range(13):
      for k in range(10):
        l=(j*10+k)%13
        dp[i+1][l]+=dp[i][j]
    for j in range(13):
      dp[i+1][j]%=mod
  else:
    k=int(S[i])
    for j in range(13):
      l=(j*10+k)%13
      dp[i+1][l]+=dp[i][j]
    for j in range(13):
      dp[i+1][j]%=mod
print(dp[len(S)][5])
### BUGGY CODE ###

n = int(input())
s = list(map(int, input().split()))
count = 0
cl = []
sm = 0
for i in range(n):
  sm+=s[i]
  cl.append(sm)

for i in range(n):
  for j in range(i, n):
    if i==0:
      if cl[j]==0:
        count+=1
    else:
      if cl[j]-cl[i-1]==0:
        count+=1
        
print(count)

### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
count = 0
dic = {}
cl = []
sm = 0
for i in range(n):
  sm+=s[i]
  if sm not in dic.keys():
    dic.update({sm:1})
  else:
    dic[sm]+=1

        
for x in dic.keys():
  t = dic[x]
  if x==0:
    count+=dic[x]
  count+=int(t*(t-1)/2)

print(count)
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
XY=[]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
for a in A[:K]:
    for b in B[:K]:
        XY.append(a+b)
XY.sort(reverse=True)
XY_prime=XY[:K]
XYZ=[]
for xy in XY_prime:
    for c in C[:K]:
        XYZ.append(xy+c)
XYZ.sort(reverse=True)
for xyz in XYZ[:K]:
    print(xyz)


### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for c in C:
    for x in xy:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])
### BUGGY CODE ###

k,s=map(int,input().split())

print(len([i for i in range(k+1)  for j in range(k+1)  for l in range(k+1) if i+j+l==s] ))

### FIXED CODE ###

k,s=map(int,input().split())

print(len([1 for z in range(k+1) for y in range(k+1) if 0<=s-y-z<=k]))
### BUGGY CODE ###

import numpy as np
n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

for i in range(q):
  a=[c[i] if b[i]==a[ii] else a[ii] for ii in range(n)]
  #print(a)
  print(sum(a))
  

### FIXED CODE ###

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
ans=sum(a)
for i in range(q):
  d[c[i]]+=d[b[i]]
  ans+=(c[i]-b[i])*d[b[i]]
  d[b[i]]=0
  print(ans)
### BUGGY CODE ###

import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt, gcd
from copy import deepcopy


def main():
    n = int(input())
    a_list = tuple(map(int, input().split()))
    num = 1000000000000000000
    ans = 1
    for i in range(n):
        ans *= a_list[i]
    
    if ans <= num:
        print(ans)
    else:
        print(-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt, gcd
from copy import deepcopy


def main():
    n = int(input())
    a_list = tuple(map(int, input().split()))
    num = 1e18
    ans = 1
    if (0 in a_list):
        print(0)
        sys.exit()
    for i in range(n):
        ans *= a_list[i]
        if ans > num:
            print(-1)
            sys.exit()

    
    if ans <= num:
        print(ans)
    else:
        print(-1)

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

# coding: utf-8

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#main
X = int(input())
F = make_divisors(X)
#intのみのlistは、直接.join()できない
S = [int(x) for x in F]

for i in range(len(S)):
    tmp = S[i]
    for A in range(tmp+1):
        B = A - tmp
        if A**5 - B**5 == X:
            print(str(A) + ' ' + str(B))
            break
    else:
        continue
    break

### FIXED CODE ###

# coding: utf-8

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#main
X = int(input())
F = make_divisors(X)
#intのみのlistは、直接.join()できない
S = [int(x) for x in F]

for i in range(len(S)):
    tmp = S[i]
    for A in range(-1000, 1001):
        B = A - tmp
        if A**5 - B**5 == X:
            print(str(A) + ' ' + str(B))
            break
    else:
        continue
    break
### BUGGY CODE ###

n_1, n_0, n_m1, k = map(int, input().split())
sum_n = 0

for i in range(k):
  if n_1 != 0:
    sum_n += 1
    n_1 -=1
  elif n_0 != 0:
    n_0 -= 1
  else:
    sum_n -= 1

print(sum_n)
    

### FIXED CODE ###

a, b, c, k = map(int, input().split())
ans = min(a, k) - max(0, k-a-b)
print(ans)
### BUGGY CODE ###

N = int(input())

l = []
for _ in range(N):
  s = input()
  if l.count(s) == 0:
    l.append(s)

print(len(l))

### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
  s = input()
  d[s]=0
  
print(len(d))
### BUGGY CODE ###

n = int(input())
ans = 1 
a = list(map(int,input().split()))
for i in a:
  ans *= i
if ans > 10**18:
  print("-1")
else:
  print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in a:
    ans = 0
else:
    for i in a:
        ans *= i
        if(ans > 10**18):
            ans = -1
            break
print(ans)
### BUGGY CODE ###

'''
B - RGB Boxes
'''

r_weight, g_weight, b_weight, N = map(int, input().split())

ans = 0
for r in range(N+1):
    for g in range(N-r*r_weight+1):
        b = (N - r*r_weight - g*g_weight) // b_weight
        if r*r_weight + g*g_weight + b*b_weight == N and b >= 0:
            ans += 1

print(ans)

### FIXED CODE ###

'''
B - RGB Boxes
'''

r_weight, g_weight, b_weight, N = map(int, input().split())

ans = 0
for r in range(N+1):
    for g in range(N-r*r_weight+1):
        rem = N - r*r_weight - g*g_weight
        if rem % b_weight == 0 and rem >= 0:
            ans += 1

print(ans)
### BUGGY CODE ###

from collections import Counter
s = input()
t_list = list(map(lambda i: int(s[-i:]) % 2019, range(1, len(s) + 1)))
t_list.append(0)
counter = Counter(t_list)
print(sum([m * (m - 1) // 2 for m in counter.values()]))

### FIXED CODE ###

s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    t %= 2019
    mod_cnt[t] += 1
    d *= 10
    d %= 2019
print(sum([m * (m - 1) // 2 for m in mod_cnt]))
### BUGGY CODE ###

n=int(input())
league=[]
for _ in range(n):
    a=list(map(int,input().split()))
    league.append(a[::-1])

total_match=n*(n-1)//2
match=0
day=0

while match<total_match:
    day+=1
    today_match=[]

    for i in range(n):
        if i in today_match:
            continue
        if league[i]:
            m=league[i][-1]-1
            if m in today_match:
                continue
            if league[m] and league[m][-1]-1==i:
                today_match.extend((league[i].pop()-1, league[m].pop()-1))
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2

print(day)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
pair = N * (N - 1) // 2
ptoi = dict()

i = 0
for x in range(1, N):
    for y in range(x + 1, N + 1):
        ptoi[(x, y)] = i
        ptoi[(y, x)] = i
        i += 1

edge = [[] for _ in range(pair)]
indeg = [0] * pair
for i in range(1, N+1):
    inp = list(map(int, input().split()))
    for s, t in zip(inp[:-1], inp[1:]):
        edge[ptoi[(i, s)]].append(ptoi[(i, t)])
        indeg[ptoi[(i, t)]] += 1


now = [i for i, d in enumerate(indeg) if d == 0]
day = 0
while now:
    nxt = []
    while now:
        s = now.pop()
        for t in edge[s]:
            if indeg[t] <= 0:
                continue
            indeg[t] -= 1
            if indeg[t] == 0:
                nxt.append(t)
    day += 1
    now = nxt

if all(i <= 0 for i in indeg):
    print(day)
else:
    print(-1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append(0)
for i in range(n-1):
    b[a[i]-1] +=1
for i in range(n):
    print(b[i])
### BUGGY CODE ###

t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    s = input()
    can = {0}

    for i in range(n - 1, -1, -1):
        c = s[i]
        a = aaa[i]
        cannot = False
        if c == '0':
            for b in list(can):
                can.add(a ^ b)
        else:
            new_can = set()
            for b in can:
                if a ^ b in can:
                    new_can.add(b)
            can = new_can
            if len(can) == 0:
                break

    if 0 in can:
        buf.append(0)
    else:
        buf.append(1)

print('\n'.join(map(str, buf)))


### FIXED CODE ###

from itertools import groupby, chain
from operator import itemgetter


def sweep(l):
    result = []
    s = set(l)
    while s:
        a = max(s)
        b = 1 << (a.bit_length() - 1)
        s = {t ^ a if t >= b else t for t in s}
        s.discard(0)
        result.append([a, b])

    return result


t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    s = input()

    if s[-1] == '1':
        buf.append(1)
        continue

    grp = [list(map(itemgetter(1), itr)) for c, itr in groupby(zip(s, aaa), key=itemgetter(0))]
    if s[0] == '0':
        grp = grp[1:]
    grp1 = grp[0::2]
    grp0 = grp[1::2]
    erasable = [False] * sum(len(g) for g in grp1)
    for i in range(len(grp1)):
        l1 = list(chain(*grp1[:i + 1]))
        l0 = list(chain(*grp0[i:]))
        s0 = sweep(l0)

        for a, b in s0:
            for i in range(len(l1)):
                if l1[i] & b:
                    l1[i] ^= a

        for j, c in enumerate(l1):
            if c == 0:
                erasable[j] = True

    if all(erasable):
        buf.append(0)
    else:
        buf.append(1)


print('\n'.join(map(str, buf)))
### BUGGY CODE ###

#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def next_kenp(node, edges, dones):
    nodes = set()
    nodes2 = set()

    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)

    for nn in nodes2:
        for n3 in edges[nn]:
            if n3 in dones or n3 in nodes:
                continue
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, input().split())
        edges[u].append(v)
    # print(edges)

    s, t = map(int, input().split())

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = next_kenp(node, edges, dones)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            if n not in dones:
                que.append((n, step + 1))
                dones.add(n)
    print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[(u, 0)].append((v, 1))
        edges[(u, 1)].append((v, 2))
        edges[(u, 2)].append((v, 0))

    s, t = map(int, input().split())

    # print(new_edges)

    dones = set()
    que = deque()
    que.append(((s, 0), 0))
    while que:
        node, step = que.popleft()

        next_nodes = edges[node]
        # print(next_nodes)
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

            if (n, l) not in dones:
                que.append(((n, l), step + 1))
                dones.add((n, l))
    print(-1)


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

n = int(input())
lis = sorted(list(map(int,input().split())))
count = 0
for i in range(n-2):
    a = i
    for j in range(1,n-1-i):
        c = n-j
        m = int((c+a)/2)
        l = i
        r = c
        if lis[a]+lis[c-1]>lis[c]:
            while r-l>1:
                if lis[m]+lis[a]>lis[c]:
                    r = m
                else:
                    l = m
                m = int((r+l)/2)
            count += c-r
print(count)

### FIXED CODE ###

import bisect
n = int(input())
lis = sorted(list(map(int,input().split())))
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        index = bisect.bisect_left(lis,lis[i]+lis[j])
        count += index-1-j
print(count)
### BUGGY CODE ###

import math
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

cnt = 0
ans = [a[0], a[1]]
for i in range(n-1):
  num = a[i]
  half = num // 2
  mx = math.factorial(num) // (math.factorial(half)*math.factorial(num-half))
  if cnt > mx:
    break
  tmp = a[i+1]
  for j in range(i+1, n):
    if abs(tmp-num/2) >= abs(a[j]-num/2):
      tmp = a[j]
    else:
      break
  mul = math.factorial(num) // (math.factorial(tmp)*math.factorial(num-tmp))
  if cnt < mul:
    cnt = mul
    ans = [num, tmp]
  if abs(a[j]-num/2) < 1:
    break
print(*ans)

### FIXED CODE ###

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

num = a[0]
tmp = a[1]
for j in range(1, n):
  if abs(tmp-num/2) >= abs(a[j]-num/2):
    tmp = a[j]
  else:
    break
ans = [num, tmp]
print(*ans)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(input())

c = []
for j in s:
    if j not in c:
        c.append(j)

g = []
for t in c:
    g.append([s.count(t),t])
g.sort(reverse=True)
h = max(g)[0]
hh = []
for ii in range(len(g)):
    if g[ii][0] == h:
        hh.append(g[ii])
    else:
        break
hh.sort(key=lambda x: x[1])
ans = []
for k in range(len(hh)):
    print(hh[k][1])

### FIXED CODE ###

import collections

n = int(input())
s = []
for i in range(n):
    s.append(input())

c = collections.Counter(s)
c_s = c.most_common()
m = c.most_common()[0][1]
ans = []
for j in range(len(c_s)):
    if c_s[j][1] != m:
        break
    else:
        ans.append(c_s[j][0])
ans.sort()
for t in ans:
    print(t)
### BUGGY CODE ###

n, k = map(int, input().split())
ans = n
if k == 1:
    print(0)
    exit()
while True:
    if ans < abs(n-k):
        break
    else:
        n = abs(n-k)
        ans = n
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
print(min(n%k, abs((n // k + 1) * k - n)))
### BUGGY CODE ###

N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
for child in sorted(children.keys()):
    used = [False]*100000
    used[ans[child]-1] = True
    for j in sorted(children[child]):
        temp = used.index(False)+1
        ans[j] = temp
        used[temp-1] = True
ans2 = [ans[b] for b in B]
print(max(ans2))
for a in ans2:
    print(a)

### FIXED CODE ###

N = int(input())
AB = [[]]*(N-1)
for i in range(N-1):
    AB[i] = list(map(int,input().split()))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
B = [0]*(N-1)
for i,ab in enumerate(AB):
    tree[ab[0]].append(ab[1])
    B[i] = ab[1]
# 各エッジの色を格納する変数の初期化
# C[0]は使わない
C = [0]*N
# 幅優先探索用のcue
Q = deque([1])
while Q:
    q = Q.popleft()
    c = 0
    for w in tree[q]:
        # 色をインクリメントした際に親の色とかぶったら更に1を加算する
        # 他は単純なインクリメント
        c += 1 + int(C[q-1] == c+1)
        # エッジの色を格納
        C[w-1] = c
        # 子供をcueに追加
        Q.append(w)
print(max(C))
for b in B:
    print(C[b-1])
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline())
L = [int(x) for x in stdin.readline().rstrip().split()]

L.sort()

tmp = 0
for i in range(N):
    for j in range(N-i-1):
        j = j + i + 1

        for k in range(N-j-1):
            k = k + j + 1

            if L[k] < L[i] + L[j]:
                tmp = tmp + 1
            else:
                break

print(tmp)

### FIXED CODE ###

# 本番では解けず。
from sys import stdin
import bisect

N = int(stdin.readline())
L = [int(x) for x in stdin.readline().rstrip().split()]

# (1)Lを昇順にソートする
L.sort()

s = 0

for i in range(N-2):
    for j in range(i+1, N-1):

        # (2)Lから2つの辺を固定で選ぶ（L[i]をa L[j]をbとする）
        # この場合、a < b + c, b < a + c はソート済みのため自明。
        # c < a + b が成り立つ棒の個数を調べる
        tmp = L[i] + L[j]

        # (3)Lの中から(2)の和(a+b)、を左に挿入できる場所二分探索で探す
        # つまりL[index - 1] < L[i] + L[j] < L[index] になるindexを探す。

        index = bisect.bisect_left(L, tmp)

        # (4) 固定で選んだ大きい方の辺から(3)で見つけた棒の間にある棒の個数を足す
        # b より右にあり、これより左にあるもの　→　開区間　(L[j], L[index])に含まれる棒は c < a + b を満たすので。
        s += (index - (j+1))

print(s)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict
from fractions import Fraction

n = int(readline())
data = list(map(int,read().split()))
mod = 1000000007

it = iter(data)
a_b = defaultdict(lambda :[0,0])
a0 = 0
b0 = 0
ab0 = 0
ans = 0
for a,b in zip(it,it):
    if(a==b==0):
        ab0 += 1
        continue
    if(a*b==0):
        if(a==0):
            a0 += 1
        if(b==0):
            b0 += 1
    else:
        if(a/b > 0):
            a = abs(a)
            b = abs(b)
            a_b[Fraction(a,b)][0] += 1
        else:
            a = abs(a)
            b = abs(b)
            a_b[Fraction(b,a)][1] += 1

exp2 = [1] * (n+1)
for i in range(n):
    exp2[i+1] = exp2[i] * 2
    exp2[i+1] %= mod


ans += (ans+1) * ( exp2[a0]-1  + exp2[b0]-1)
ans %= mod

for key,val in a_b.items():
    ans += (ans+1) * ( exp2[val[0]]-1  + exp2[val[1]]-1)
    ans %= mod

ans += ab0
ans %= mod

print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict
from math import gcd

n = int(readline())
data = list(map(int,read().split()))
mod = 1000000007

it = iter(data)
a_b = defaultdict(lambda :[0,0])
a0 = 0
b0 = 0
ab0 = 0
ans = 0
for a,b in zip(it,it):
    if(a==b==0):
        ab0 += 1
        continue
    if(a*b==0):
        if(a==0):
            a0 += 1
        if(b==0):
            b0 += 1
    else:
        if(a/b > 0):
            a = abs(a)
            b = abs(b)
            gcd_num = gcd(a,b)
            a_b[(a//gcd_num,b//gcd_num)][0] += 1
        else:
            a = abs(a)
            b = abs(b)
            gcd_num = gcd(a,b)
            a_b[(b//gcd_num,a//gcd_num)][1] += 1

exp2 = [1] * (n+1)
for i in range(n):
    exp2[i+1] = exp2[i] * 2
    exp2[i+1] %= mod


ans += (ans+1) * ( exp2[a0]-1  + exp2[b0]-1)
ans %= mod

for key,val in a_b.items():
    ans += (ans+1) * ( exp2[val[0]]-1  + exp2[val[1]]-1)
    ans %= mod

ans += ab0
ans %= mod

print(ans)
### BUGGY CODE ###

import itertools
N=int(input())
S=input()
ans=0
L=dict()
R=dict()
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    T3=""
    for i in range(N):
        if seq[i]==0:
            T0+=S[i]
            T2+=S[-i-1]
        else:
            T1+=S[i]
            T3+=S[-i-1]
    a0=len(T0)
    a1=len(T1)
    a2=len(T2)
    a3=len(T3)
    L[(T0,T1)]=L.get((T0,T1),0)+1
    R[(T2,T3)]=R.get((T2,T3),0)+1
for tup in L:
    if tup in R:
        ans+=L[tup]*R[tup]
print(ans)


### FIXED CODE ###

import itertools
import bisect
N=int(input())
S=input()
ans=0
L=dict()
R=dict()
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    T3=""
    for i in range(N):
        if seq[i]==0:
            T0+=S[i]
            T2+=S[-i-1]
        else:
            T1+=S[i]
            T3+=S[-i-1]
    a0=len(T0)
    a1=len(T1)
    a2=len(T2)
    a3=len(T3)
    if (T0,T1) in L:
        L[(T0,T1)]+=1
    else:
        L[(T0,T1)]=1
    if (T2,T3) in R:
        R[(T2,T3)]+=1
    else:
        R[(T2,T3)]=1
for tup in L:
    if tup in R:
        ans+=L[tup]*R[tup]
print(ans)