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

N, P = map(int, input().split())
ans = 1
def main(n, p):
  global ans
  for i in range(2, int(p**(1/n))+4):
    t = i**n
    if p % t == 0:
      ans *= i
      return main(n, p//t)
  return ans

print(main(N, P))

### FIXED CODE ###

N, P = map(int, input().split())
ans = 1
def main(n, p):
  if n == 1:
    return P
  global ans
  for i in range(2, int(p**(2/n))):
    t = i**n
    if p % t == 0:
      ans *= i
      return main(n, p//t)
  return ans

print(main(N, P))
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())

G = [[] for i in range(n)]


def bfs(s, e):
    check, dist = [0 for i in range(n)], [-1 for i in range(n)]
    q = deque()

    check[s], dist[s] = 1, 0
    q.append(s)

    while len(q) != 0:
        u = q.popleft()
        for v in range(len(G[u])):
            if check[G[u][v]] == 0:
                check[G[u][v]], dist[G[u][v]] = 1, dist[u] + 1
                q.append(G[u][v])

        check[u] = 2

    return dist[e]


def main():
    for i in range(m):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)

    q = int(input())

    for i in range(q):
        s, t = map(int, input().split())
        k = bfs(s, t)
        if k == -1:
            print("no")
        else:
            print("yes")


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())

G = [[] for i in range(n)]
check = [0 for i in range(n)]


def bfs(s, c):
    q = deque()

    check[s] = 1
    q.append(s)

    while len(q) != 0:
        u = q.popleft()
        for v in range(len(G[u])):
            if check[G[u][v]] == 0:
                check[G[u][v]] = 1
                q.append(G[u][v])

        check[u] = c


def main():
    for i in range(m):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)

    cnt = 2
    for i in range(n):
        if check[i] == 0:
            bfs(i, cnt)
            cnt += 1

    q = int(input())
    for i in range(q):
        s, t = map(int, input().split())
        if check[s] == check[t]:
            print("yes")
        else:
            print("no")


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

n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0] * (w + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    wi, vi = wv[i - 1]
    for j in range(w + 1):
        if j < wi:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + vi)
print(dp[n][w])


### FIXED CODE ###

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

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
# dp[n][w] = n番目までの品物による重量w以下の価値の総和の最大値

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j - w >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[N][W])
### BUGGY CODE ###

def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)

selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])

scorelist = []
scorelist.append(score)
front_pointer = k - 1
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for p in range(front_pointer,-1,-1):
        item = selected[p]
        if([elem for elem in selected if(elem[0]==item[0] and elem is not item)]):
            score -= item[1]
            selected.remove(item)
            front_pointer = p - 1
            break

    #add the largest one that add kind
    for j in range(pointer,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            pointer = j + 1            
            score += 2*startKindNum + 1 + sushi[j][1]
            startKindNum += 1
            scorelist.append(score)
            break
print(max(scorelist))


### FIXED CODE ###

def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)
'''
selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])
maxscore = score
front_pointer = k - 1
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for p in range(front_pointer,-1,-1):
        item = selected[p]
        flag = False
        for idx in range(p):
            if(selected[idx][0]==item[0]):
                score -= item[1]
                selected.remove(item)
                front_pointer = p - 1
                flag = True
                break
        if(flag):
            break

    #add the largest one that add kind
    for j in range(pointer,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            pointer = j + 1            
            score += 2*startKindNum + 1 + sushi[j][1]
            if(score>maxscore):
                maxscore = score
            startKindNum += 1
            break
'''
kindset = set([])
score = 0
extras = []
for item in sushi[:k]:
    if item[0] in kindset:
        extras.append(item[1])
    else:
        kindset.add(item[0])
    score += item[1]
score += len(kindset)**2
maxscore = score
for item in sushi[k:]:
    if not  extras:
        break
    if item[0] in kindset:
        continue
    score += (item[1] - extras.pop()) + 2*len(kindset) + 1
    kindset.add(item[0])
    #print(score)
    if score > maxscore:
        maxscore = score


print(maxscore)
### BUGGY CODE ###

def anotherpair(x, y):                
    l = []
    c=1
    for i in range(x, y+1):
        if c==0:
            l.append([i, i-1])
        c=0
    return l
n, a, b = map(int, input().split())
if n==1:
    if a==b:
            ans = 1
    else:
        ans = 0
else:
    if a>b:
        ans = 0
    else:
        ans = len(anotherpair((n-2)*a, (n-2)*b))+1
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
if n==1:
    if a==b:
            ans = 1
    else:
        ans = 0
else:
    if a>b:
        ans = 0
    else:
        ans = ((n-2)*b-(n-2)*a)+1
print(ans)
### BUGGY CODE ###

N = input()
vals = map(int, input().split())
count = 0
is_odd = False
while True:
    for val in vals:
        if val % 2 == 1:
            is_odd = True
    if is_odd:
        break
    vals = map(lambda x: x/2, vals)
    count += 1
print (count)

### FIXED CODE ###

N = int(input())
vals = list(map(int, input().split()))
count = 0
is_odd = False
while True:
    for i in range(0, N):
        if vals[i] % 2 == 1:
            is_odd = True
        vals[i] /= 2
    if is_odd:
        break
    count += 1
print (count)
### BUGGY CODE ###

#!/usr/bin/env python3
S = input().strip()
N = len(S)
SS = S[::-1]

mod_count = [0] * 2019
mod_count[0] = 1
sums = [0]
for i in range(N):
    sums.append((sums[-1] + int(SS[i]) * (10**i)) % 2019)
    mod_count[sums[-1]] += 1

print(sum([m * (m - 1) for m in mod_count]) // 2)

### FIXED CODE ###

#!/usr/bin/env python3


def main():
    S = input()
    N = len(S)

    mod_count = [0] * 2019
    mod_count[0] = 1
    ssum = 0
    for i, c in enumerate(S[::-1]):
        ssum = (ssum + int(c) * pow(10, i, 2019)) % 2019
        mod_count[ssum] += 1

    print(sum([m * (m - 1) for m in mod_count]) // 2)


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

N,M = map(int,input().split())
p = [0] + [int(x) for x in input().split()]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:    return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:    self.rank[x] += 1

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

UF = UnionFind(N)
for _ in range(M):
    x,y = map(int,input().split())
    UF.union(x, y)

unionUF, unionp, par = [], [], []
for i in range(1, N+1):
    temp = UF.find(i)
    if temp in par:
        unionUF[par.index(temp)].add(i)
        unionp[par.index(temp)].add(p[i])
    else:
        par.append(temp)
        unionUF.append(set([i]))
        unionp.append(set([p[i]]))

ans = 0
for i in range(len(unionUF)):
    ans += len(unionUF[i] & unionp[i])
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
p = [0] + [int(x) for x in input().split()]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:    return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:    self.rank[x] += 1

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

UF = UnionFind(N)
for _ in range(M):
    x,y = map(int,input().split())
    UF.union(x, y)

unionUF, unionp = [set() for _ in range(N+1)], [set() for _ in range(N+1)]
for i in range(1, N+1):
    temp = UF.find(i)
    unionUF[temp].add(i)
    unionp[temp].add(p[i])

ans = 0
for i in range(len(unionUF)):
    ans += len(unionUF[i] & unionp[i])
print(ans)
### BUGGY CODE ###

from collections import defaultdict

n, m = map(int, input().split())

pen_dic=defaultdict(lambda: 0)
ac=set()

for _ in range(m):
  p, s = input().split()
  if p in set(ac):
    continue

  if s == "AC":
    ac.add(p)
  else:
    pen_dic[p] += 1
print(len(set(ac)), sum(pen_dic[str(i)] for i in list(ac)))

### FIXED CODE ###

import sys
from collections import defaultdict

n, m = map(int, input().split())

wa=defaultdict(lambda: 0)
already=set()
ac = 0
for line in sys.stdin:
  p, s = line.split()
  p = int(p)
  if p in already:
    continue

  if s == "AC":
    ac+=1
    already.add(p)
  else:
    wa[p] += 1

print(ac, sum(wa[i] for i in already))
### BUGGY CODE ###

K, S = map(int, input().split())
ret = 0
for x in range(K + 1):
    for y in range(K + 1):
        if x + y > S:
            break
        for z in range(K + 1):
            if x + y + z == S:
                ret += 1
            if x + y + z >= S:
                break

print(ret)

### FIXED CODE ###

K, S = map(int, input().split())
ret = 0
for x in range(K + 1):
    for y in range(K + 1):
        if x + y <= S and  S - x - y <= K:
            ret += 1

print(ret)
### BUGGY CODE ###

N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for i in range(N)]

w = [w_v[i][0] for i in range(N)]
v = [w_v[i][1] for i in range(N)]

#dp[i+1][j]:i番目までの品物で重さがjとなるときの価値の総和

dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for i in range(N)]

w = [w_v[i][0] for i in range(N)]
v = [w_v[i][1] for i in range(N)]

#dp[i+1][j]:i番目までの品物で重さがjとなるときの価値の総和

dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])
### BUGGY CODE ###

def f_d():
    n, k = map(int, input().split())
    *s, = map(int, list(input()))
    l, t, c = [], 1, 0
    for i in range(n):
        if s[i]==t:
            c += 1
        else:
            l.append(c)
            c, t = 1, t^1
    if c!=0:
        l.append(c)
    if len(l)%2==0:
        l.append(0)

    r, a = 2*k+1, 0
    for i in range(0, len(l), 2):
        a = max(a, sum(l[i:min(i+r, len(l))]))
    print(a)

if __name__ == "__main__":
    f_d()


### FIXED CODE ###

def f_d():
    n, k = map(int, input().split())
    *s, = map(int, list(input()))
    l, t, c = [], 1, 0
    for i in range(n):
        if s[i]==t:
            c += 1
        else:
            l.append(c)
            c, t = 1, t^1
    if c!=0:
        l.append(c)
    if len(l)%2==0:
        l.append(0)

    r, a = 2*k+1, 0
    li = ri = tmp = 0
    for i in range(0, len(l), 2):
        nli, nri = i, min(i+r, len(l))
        while li<nli:
            tmp -= l[li]
            li += 1
        while ri<nri:
            tmp += l[ri]
            ri += 1
        a = max(a, tmp)
    print(a)

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

import copy
n=int(input())
l=list(map(int,input().split()))
cl=copy.deepcopy(l)
l.sort()
for i in range(n):
  tmp=cl[i]
  l.remove(tmp)
  print(l[n//2-1])
  l.append(tmp)
  l.sort()

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
list=sorted(l)
for i in range(n):
  if l[i]<=list[n//2-1]:
    print(list[n//2])
  else:
    print(list[n//2-1])
### BUGGY CODE ###

from bisect import bisect_right
def getVal(i):  # get value of node (i,i)
    v = T[(i,i)][0]
    cur = (i,i)
    cur = T[cur][1]
    while cur[0]>=0:
        v += T[cur][0]
        cur = T[cur][1]
    return v
def udT(i,j,x,node):  # add x between [i,j] where current node is given
    l,r = node[0],node[1]
    if i<=l and r<=j:
        T[node][0] += x
    elif i>r or j<l:
        return
    else:
        udT(i,j,x,T[node][2])
        udT(i,j,x,T[node][3])
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
n = 0
m = N
while m>0:
    m = m//2
    n += 1
if N==2**(n-1):
    n -= 1
for i in range(N,2**n):  # fill in the remainder of N
    X.append([X[-1][0]+1,0])
# Construction of Tree
Y = [X[i][0] for i in range(N)]  # Tree structure
if N>1:
    T = {(i,i):[X[i][1],(i,i+1) if i%2==0 else (i-1,i),(-1,-1),(-1,-1)] for i in range(2**n)}  # T[node] = [value,parent,left_child,right_child]
else: # N==1
    T = {(i,i):[X[i][1],(-1,-1),(-1,-1),(-1,-1)] for i in range(2**n)}  # T[node] = [value,parent,left_child,right_child]
for h in range(n):
    for i in range(2**h):
        d = 2**(n-h)  # interval length of each node
        if h==0:
            T[(i*d,(i+1)*d-1)] = [0,(-1,-1),(i*d,i*d+d//2-1),((i+1)*d-d//2,(i+1)*d-1)]
        else:
            T[(i*d,(i+1)*d-1)] = [0,(i*d,i*d+2*d-1) if (i*d)%2**(n-h+1)==0 else ((i+1)*d-2*d,(i+1)*d-1),(i*d,i*d+d//2-1),((i+1)*d-d//2,(i+1)*d-1)]
cnt = 0
cur = 0
while cur<N:
    x = Y[cur]
    v = getVal(cur)
    if v%A==0:
        k = v//A
    else:
        k = v//A+1
    ind = bisect_right(Y,x+2*D)
    udT(cur,ind-1,-k*A,(0,2**n-1))
    cnt += k
    flag = 0
    for i in range(cur+1,N):
        if getVal(i)>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)

### FIXED CODE ###

from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
flag = 0
while cur<N:
    x = X[cur][0]
    h = X[cur][1]+delta
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,N):
        delta += B[i]
        B[i] = 0
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)
### BUGGY CODE ###

import itertools
N, Ma, Mb = map(int, input().split())
r = Ma/Mb
costlist = []
data = [list(map(int, input().split())) for i in range(N)]
for i in range(1, N+1):
    combination = list(itertools.combinations(data, i))
    for k in range(len(combination)):
        a_tot = 0
        b_tot = 0
        c_tot = 0
        for j in range(len(combination[k])):
            a_tot += combination[k][j][0]
            b_tot += combination[k][j][1]
            c_tot += combination[k][j][2]
        if a_tot/b_tot == r:
            costlist.append(c_tot)
if costlist == []:
    print(-1)
else:
    print(min(costlist))


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
r = Ma/Mb
a = 0
b = 0
costlist = [500000]
data = [list(map(int, input().split())) for i in range(N)]
for i in range(N):
    a += data[i][0]
    b += data[i][1]


dp = [[[500000 for i in range(N+1)] for i in range(b+10)] for i in range(a+10)]
dp[0][0][0] = 0

#Aがiグラム、Bがjグラム、k番目までの薬を用いたときの最小コスト
for k in range(N):
    for j in range(b):
        for i in range(a):
            ai = data[k][0]
            bj = data[k][1]
            dp[i+ai][j+bj][k+1] = min(dp[i+ai][j+bj][k+1], dp[i][j][k] + data[k][2])
            dp[i][j][k+1] = min(dp[i][j][k], dp[i][j][k+1])

for i in range(1, a):
    for j in range(1, b):
        if i/j == r:
            costlist.append(dp[i][j][N])
if N == 1:
    if data[0][0]/data[0][1] == r:
        print(data[0][2])
    else:
        print(-1)

elif min(costlist) == 500000:
    print(-1)
else:
    print(min(costlist))
### BUGGY CODE ###

import copy
 
#  print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))
 
n, t = map(int, input().split())
L = [int(i) for i in input().split()]
LL = copy.deepcopy(L)
 
minvalue = L[0]
maxvalue = max(LL)
subt = 0
count = 1
flag = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  LL = LL[1:]
  if maxvalue == L[i]:
    maxvalue = max(LL)
 
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
 
print(count)

### FIXED CODE ###

import copy
 
n, t = map(int, input().split())
L = [int(i) for i in input().split()]

LL = [[0] for i in range(n)]
tmax = L[-1]
for i in range(n):
  if tmax <= L[-i-1]:
    tmax = L[-i-1]
  LL[-i-1] = tmax
 
minvalue = L[0]
maxvalue = LL[0]
subt = 0
count = 1
flag = 0
flagg = 0
j = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  
  maxvalue = LL[i]
 
  #if maxvalue == L[i]:
    #LL = LL[i-j+1:]
    #maxvalue = max(LL)
    #j = i+1
 
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
  #print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))
 
print(count)
### BUGGY CODE ###

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = True

    try:

        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:


        return array_result

arr_data = getinputdata()

#島数
n = arr_data[0][0]
m = int(arr_data[0][1])

arr01 = []
arr02 = []
for i in range(1, 1 + m):

    if arr_data[i][0] == "1":
        
        arr01.append(arr_data[i][1])

    if arr_data[i][1] == n:
        
        arr02.append(arr_data[i][0])

chkflg = False
for v in arr01:
    
    if v in arr02:
        
        chkflg = True
        break
        
print("POSSIBLE" if chkflg else "IMPOSSIBLE")

### FIXED CODE ###

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = True

    try:

        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:


        return array_result

arr_data = getinputdata()

#島数
n = arr_data[0][0]
m = int(arr_data[0][1])

arr01 = []
arr02 = []
for i in range(1, 1 + m):

    if arr_data[i][0] == "1":
        
        arr01.append(arr_data[i][1])

    if arr_data[i][1] == n:
        
        arr02.append(arr_data[i][0])


print("POSSIBLE" if len(list(set(arr01) & set(arr02))) == 1 else "IMPOSSIBLE")
### BUGGY CODE ###

def main():
	k = int(input())
	h = list(map(int,input().split()))
	ans = 1
	for i in range(k):
		ans *= h[i]

	if ans <= 10**18:
		print(ans)
	else:
		print(-1)


if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	k = int(input())
	h = tuple(map(int,input().split()))
	ans = 1
	avoid = 0
	if (0 in h):
		print(0)
	else:
		for i in range(k):
			ans = h[i] * ans
			if ans > 10 **18:
				print(-1)
				avoid = 1
				break
		if avoid == 0:
			print(ans)
	


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

n,k,q=list(map(int,input().split()))
a=[]
for i in range(q):
  a.append(int(input()))
p=[k for _ in range(n)]
w=q-k+1
for i in range(n):
  if a.count(i+1) >= w:
    print('Yes')
  else:
    print('No')


### FIXED CODE ###

n,k,q=list(map(int,input().split()))
a=[0 for _ in range(n)]
for i in range(q):
  x=int(input())
  a[x-1] += 1
w=q-k+1
for i in range(n):
  if a[i] >= w:
    print('Yes')
  else:
    print('No')
### BUGGY 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)


def main():
    n = I()
    a = [LI() for _ in range(n)]
    s = collections.defaultdict(int)
    s[0] = 1
    ii = [2**i for i in range(n)]
    for i in range(n):
        t = collections.defaultdict(int)
        b = [ii[c] for c in range(n) if a[i][c]]
        for k,v in s.items():
            v = v % mod
            for j in b:
                if not (j & k):
                    t[k | j] += v
        s = t

    if len(s) == 0:
        return 0

    return list(s.values())[0] % mod


print(main())


### FIXED 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)


def main():
    n = I()
    a = [LI() for _ in range(n)]
    m = 2**n
    s = [[0] * m for _ in range(n+1)]
    s[0][0] = 1
    ii = [2**i for i in range(n)]
    for i in range(n):
        t = s[i+1]
        u = s[i]
        b = [ii[c] for c in range(n) if a[i][c]]
        for k in range(m):
            v = u[k]
            v = v % mod
            if v < 1:
                continue
            for j in b:
                if not (j & k):
                    t[k | j] += v

    return s[-1][-1] % mod


print(main())
### BUGGY CODE ###

T = str(input())
PD = 0

for i in range(int(T.count('?'))+1):
    T1 = T.replace('?','D',i)
    T1 = T1.replace('?','P')
    PD1 = T1.count('D') + T1.count('PD')
    if PD1 > PD:
        T2 = T1

print(T2)

### FIXED CODE ###

T = str(input())

T = T.replace('P?','PD')
T = T.replace('?','D')

print(T)