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

n,m = map(int,input().split())
edge = [[] for _ in [0]*n]
for _ in range(m):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)


new = [[i] for i in range(n)]
res = []
res2 = -1

while len(new) > 0:
    tank = []
    for i in range(len(new)):
        el = new[i]

        for go in edge[el[-1]]:
            if not go in el:
                if el[0] in edge[go]:
                    print(len(el)+1)
                    for e in el:
                        print(e+1)
                    print(go+1)

                    exit()
                tank.append(el+[go])
    new = tank
    
print(-1)



### FIXED CODE ###

import sys
input = sys.stdin.readline

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

edge = [[] for _ in [0]*n]
back = [[] for _ in [0]*n]

for _ in [0]*m:
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    back[b-1].append(a-1)


res = [None]*(n+1)

for end in range(n):
    for start in edge[end]:
        cost = [-1]*n
        cost[start] = 0
        new = [start]
        tank = []
        judge = True

        while len(new) > 0 and judge:
            tank = []
            for fr in new:
                for go in edge[fr]:
                    if cost[go] < 0:
                        cost[go] = cost[fr] + 1
                        tank.append(go)
                        if go == end:
                            judge = False
            new = tank

        
        if cost[end] >= 0 and cost[end] < len(res):
            p = end
            res = [p+1]
            while p != start:
                for e in back[p]:
                    if cost[p] == cost[e]+1:
                        p = e
                        res.append(p+1)
                        break
if res[0] == None:
    print(-1)
else:                      
    print(len(res))
    for e in res:
        print(e)
### BUGGY CODE ###

exec("def nWord(): nWord.cache = raw_input() if not hasattr(nWord, 'cache') or nWord.cache=='' else nWord.cache ; pos = nWord.cache.find(nWord.sep) ; ret, nWord.cache = (nWord.cache, '') if pos==-1 else (nWord.cache[:pos], nWord.cache[pos+1:].lstrip(nWord.sep)) ; return ret") ; exec("nWord.sep = ' '") ; exec("def ___nLine2(): ret, nWord.cache = (raw_input(), nWord.cache if hasattr(nWord, 'cache') else '') if not hasattr(nWord, 'cache') or nWord.cache=='' else (nWord.cache, '') ; return ret") ; exec('def nInt(): return int(nWord())') ; exec('def nFloat(): return float(nWord())') ; exec("def ___nAuto2():\n ret = nWord()\n try: return int(ret)\n except: pass\n try: return float(ret)\n except: return ret") ; exec("def nAuto(n=None): return ___nAuto2() if n is None else [___nAuto2() for i in range(n)]") ; exec("def nLine(n=None): return ___nLine2() if n is None else [___nLine2() for i in range(n)]")

A = nAuto(nAuto())

A.reverse()
A.append(0)
A.reverse()

for i in range(1, len(A)):
    A[i] = A[i] + A[i-1]

dic = {}

cnt = 0
for i in A:
    if i not in dic:
        dic[i] = 1
    else:
        cnt += dic[i]
        dic[i] += 1
print(cnt)


### FIXED CODE ###

exec("def nWord(): nWord.cache = raw_input() if not hasattr(nWord, 'cache') or nWord.cache=='' else nWord.cache ; pos = nWord.cache.find(nWord.sep) ; ret, nWord.cache = (nWord.cache, '') if pos==-1 else (nWord.cache[:pos], nWord.cache[pos+1:].lstrip(nWord.sep)) ; return ret") ; exec("nWord.sep = ' '") ; exec("def ___nLine2(): ret, nWord.cache = (raw_input(), nWord.cache if hasattr(nWord, 'cache') else '') if not hasattr(nWord, 'cache') or nWord.cache=='' else (nWord.cache, '') ; return ret") ; exec('def nInt(): return int(nWord())') ; exec('def nFloat(): return float(nWord())') ; exec("def ___nAuto2():\n ret = nWord()\n try: return int(ret)\n except: pass\n try: return float(ret)\n except: return ret") ; exec("def nAuto(n=None): return ___nAuto2() if n is None else [___nAuto2() for i in range(n)]") ; exec("def nLine(n=None): return ___nLine2() if n is None else [___nLine2() for i in range(n)]")

nAuto()
A = [int(i) for i in raw_input().split(' ')]

A.reverse()
A.append(0)
A.reverse()

for i in range(1, len(A)):
    A[i] = A[i] + A[i-1]

dic = {}

cnt = 0
for i in A:
    if i not in dic:
        dic[i] = 1
    else:
        cnt += dic[i]
        dic[i] += 1
print(cnt)
### BUGGY CODE ###

N=int(input())
a = list(map(int, input().split()))
import fractions
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
import numpy as np
aa = np.array(a)
print(sum(ans//aa)%(10**9+7))

### FIXED CODE ###

from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm, i)
ans = 0
for i in a:
    ans += (lcm//i)#%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

n= int(input())
A = list(map(int, input().split()))
q = int(input())
Mi = list(map(int, input().split()))

def solve(i,m):
 if m == 0:
  return True
 if i >= n:
  return False
 res = solve(i+1, m) or solve(i + 1, m - A[i])
 return res

for m in Mi:
 if solve(0, m):
  print("yes")
 else:
  print("no")

### FIXED CODE ###

n= int(input())
A = list(map(int, input().split()))
q = int(input())
Mi = map(int, input().split())
PS={}
def solve(i,m):
 if m == 0:
  return True
 if (i,m) in PS:
  return PS[(i,m)]
 if i >= n:
  return False
 res = solve(i+1, m) or solve(i + 1, m - A[i])
 PS[(i,m)] = res
 return res

for m in Mi:
 if solve(0, m):
  print("yes")
 else:
  print("no")
### BUGGY CODE ###

N = int(input())
As = sorted(list(map(int, input().split())))
A = As.pop()
N -= 1
between = [A]

ans = 0
while N > 0:
  point = between.pop()
  ans += point

  A = As.pop()
  N -= 1
  between = [A, A] + between
print(ans)

### FIXED CODE ###

N = int(input())
As = sorted(list(map(int, input().split())), reverse = True)
ans = As[0]
N -= 2

p = N // 2
ans += sum(As[1:1+p]) * 2

if N % 2 == 1:
  ans += As[1+p]

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

import sys
from collections import Counter
from math import factorial

N = int(input())
S = input()

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = [0]*(2*N)
op[0] = False
ct_L = 1
ans = 1
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        if op[i-1] is False:
            op[i] = True
            ans *= ct_L
            ct_L -= 1
        else:
            op[i] = False
            ct_L += 1
    else:
        if op[i-1] is False:
            op[i] = False
            ct_L += 1
        else:
            op[i] = True
            ans *= ct_L
            ct_L -= 1

ct_L, ct_R = Counter(op).values()
if ct_L != ct_R:
    print(0)
    sys.exit()

mod = 10**9+7
print(factorial(N) * ans % mod)


### FIXED CODE ###

import sys
from math import factorial

N = int(input())
S = input()
mod = 10**9+7

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = "L"
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        op += 'R' if op[i-1] == 'L' else 'L'
    else:
        op += 'R' if op[i-1] == 'R' else 'L'

if op.count('L') != N:
    print(0)
    sys.exit()

ct_L, ans = 0, 1

for i in op:
    if i == 'L':
        ct_L += 1
    else:
        ans *= ct_L
        ct_L -= 1
    ans %= mod


print(factorial(N) * ans % mod)
### BUGGY CODE ###

# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        networks[person] = set()
        stack = deque([person])
        while stack:
            new = stack.pop()
            visited[new] = True
            net_leaders[new] = person
            networks[person].add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack.append(adj)

    answers = []
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers.append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        network_add = network.add
        stack = [person]
        stack_append = stack.append
        stack_pop = stack.pop
        while stack:
            new = stack_pop()
            visited[new] = True
            net_leaders[new] = person
            network_add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack_append(adj)
        networks[person] = network

    answers = []
    answers_append = answers.append
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers_append(ans)

    print(*answers)
    return


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

n=int(input())

dic={}
for i in range(n):
    s=input()
    if s not in dic:
        dic[s]=1
    else:
        dic[s]+=1

keys=sorted([k for k,v in dic.items() if v==max(dic.values()) ])
for i in keys:
    print(i)

### FIXED CODE ###

n=int(input())

dic={}
for i in range(n):
    s=input()
    if s not in dic:
        dic[s]=1
    else:
        dic[s]+=1
dic2=sorted(dic.items(), key=lambda x:x[1],reverse=True)
ma=dic2[0][1]

keys=sorted([k for k,v in dic.items() if v==ma])
for i in keys:
    print(i)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
#dp[i] をiまでの最小コスト
INF = 10**9
h.extend([INF for i in range(1000)])
dp = [INF for i in range(N+1000)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        dp[i + k] = min(dp[i + k], dp[i] + abs(h[i+k] - h[i])) # i => i+k でのコストの更新
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
#dp[i] をiまでの最小コスト
INF = 10**9
# h.extend([INF for i in range(100)])
dp = [INF for i in range(N)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i + k >= N:
            break
        dp[i + k] = min(dp[i + k], dp[i] + abs(h[i+k] - h[i])) # i => i+k でのコストの更新
print(dp[N-1])
### BUGGY CODE ###

n = int(input())
a = []
ans = 0
for i in range(n):
    a.append(int(input()))
set_a = set(a)
for i in set_a:
    ans += a.count(i) % 2
print(ans)

### FIXED CODE ###

n = int(input())
evole = set()
ans = 0
for i in range(n):
    var = int(input())
    if var in evole:
        evole.remove(var)
        ans -= 1
    else:
        evole.add(var)
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = [s]
    ans = k
    Qappend = Q.append
    searched = [0 for i in range(n+1)]
    searched[s] = 1
    v = Q.pop()

    cand = k - 1
    for i in g[v]:
        searched[i] = 1
        ans *= cand
        cand -= 1
        Qappend(i)
        ans = ans % MOD

    while len(Q) != 0:
        v = Q.pop()
        cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans *= cand
            cand -= 1
            Qappend(i)
        ans = ans % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)


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

import collections

n=int(input())
l=[]
for _ in range(n):
    l.append(input())

c=collections.Counter(l)
cc=c.most_common()
ccc=[]
for j in cc:
    if j[1]==max(c.values()):
        ccc.append(j[0])

for k in sorted(ccc):
    print(k)

### FIXED CODE ###

import collections

n=int(input())
l=[]
for _ in range(n):
    l.append(input())

c=collections.Counter(l)
cc=c.most_common()
ccc=[]
for j in cc:
    if j[1]==cc[0][1]:
        ccc.append(j[0])

for k in sorted(ccc):
    print(k)
### BUGGY CODE ###

from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n):
    ans=(ans+(x[-1]-x[i])*(Fraction(1,i+1)))%(10**9+7)

for i in range(1,n):
    ans=ans*i%(10**9+7)
print(ans)


### FIXED CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
ans=math.factorial(n-1)%(10**9+7)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

c=0
for i in range(1,n):
    c+=(a[-1]-a[i-1])*modinv(i, mod=10**9+7)
print(ans*c%(10**9+7))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	N = int(input())
	A = input().split()
	A = [int(s) for s in A]

	base = -1
	for i, val in enumerate(A):
		if i == 0:
			base == val
			continue
		base = gcd(val, base)

	ans = base
	for i, val in enumerate(A):
		tmp = -1
		if ans >= val:
			break
		for j, vol in enumerate(A):
			if i == j:
				continue
 
			if tmp == -1:
				tmp = vol
				continue
 
			tmp = gcd(vol, tmp)
			if tmp <= ans:
				break
 
		if tmp > ans:
			ans = tmp
 
	print(ans)
 
 
 
def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
	
def main():
	N = int(input())
	A = list(map(int, input().split(" ")))
	
	L = []
	for i, val in enumerate(A):
		if i == 0:
			L.append(val)
			continue
		tmp = gcd(val, L[i-1])
		L.append(tmp)
		
	R = []
	for i, val in enumerate(reversed(A)):
		if i == 0:
			R.append(val)
			continue
		tmp = gcd(val, R[i-1])
		R.append(tmp)
		
	ans = 0
	for i, val in enumerate(A):
		if i == 0:
			tmp = R[len(A)-2]
		elif i == len(A)-1:
			tmp = L[len(A)-2]
		else:
			tmp = gcd(L[i-1], R[len(A)-i-2])
			
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

n = input()
st = input()

N = n.split(' ')[0]
Q = int(n.split(' ')[1])

for i in range(0, Q):
    n = input()
    l = int(n.split(' ')[0])
    r = int(n.split(' ')[1])
    partial = st[l-1:r]
    count = 0
    while partial.find('AC') != -1:
        partial = partial.replace('AC', '', 1)
        count += 1
    print(count)

### FIXED CODE ###

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

cum=[0]*n
for i in range(1, n):
    cum[i] = cum[i - 1]
    if s[i-1:i+1] == 'AC':
        cum[i]+=1

for i in range(q):
    print(cum[a[i][1]-1]-cum[a[i][0]-1])
### BUGGY CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(501)] for _ in range(501)] 
  for _ in range(M):
    l, r = map(int, input().split())
    for i in range(1, l+1):
      for j in range(r, 501):
        DP[i][j] += 1

  for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    print(DP[p][q])


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(N+1)] for _ in range(N+1)] 
  for _ in range(M):
    l, r = map(int, input().split())
    DP[l][r] += 1

  cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
  for i in range(1, N+1):
    for j in range(1, N+1):
      cum[i][j] = DP[i][j] + cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1]

  for _ in range(Q):
    p, q = map(int, input().split())
    print(cum[q][q] - cum[p-1][q] - cum[q][p-1] + cum[p-1][p-1])


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

import itertools
N, K = map(int, input().split())
x = list(map(int, input().split()))
ans = 10 ** 8 * K
for i in range(N-K+1):
  for j in range(i+(K-1), N):
    a = abs(x[i]) + abs(x[i] - x[j])
    b = abs(x[j]) + abs(x[i] - x[j])
    if min(a, b) < ans:
      ans = min(a, b)
print(ans)

### FIXED CODE ###

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

ans = float('inf')
for i in range(n-k+1):
    l, r = X[i], X[i+k-1]
    if r <= 0:
        ans = min(abs(l), ans)
    elif 0 <= l:
        ans = min(abs(r), ans)
    else:
        dist = min(abs(l), abs(r))*2+max(abs(l), abs(r))
        ans = min(dist, ans)
print(ans)
### BUGGY CODE ###

import sys
h, w, a, b = [int(i) for i in sys.stdin.readline().split()]
res = ""
for y in range(b):
    res += "0" * a + "1" * (w - a)
    res += "\n"
for y in range(h-b):
    res += "1" * a + "0" * (w - a)
    res += "\n"
print(res)

### FIXED CODE ###

import sys
h, w, a, b = [int(i) for i in sys.stdin.readline().split()]
res = []
res.append(("0" * a + "1" * (w - a) + "\n") * b)
res.append(("1" * a + "0" * (w - a) + "\n") * (h-b))
print("".join(res))
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            d = math.gcd(a, b)
            ans += math.gcd(c, d)

print(ans)

### FIXED CODE ###

import math
from _functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, b, c)

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

from functools import lru_cache
import sys

H,N = [int(i) for i in input().rstrip().split(' ')]
M = [[int(i) for i in input().rstrip().split(' ')] for _ in range(N)]
#print(*M, sep='\n') #配列開業表示の仕方
sys.setrecursionlimit(10**9)
@lru_cache(maxsize=None)
def DP(hp):
    global M
    if hp <= 0:
        return 0
    res = min([DP(hp-a)+b for a,b in M])
    return res

print(DP(H))

### FIXED CODE ###

from functools import lru_cache
import sys

H,N = [int(i) for i in input().rstrip().split(' ')]
M = [[int(i) for i in input().rstrip().split(' ')] for _ in range(N)]

sys.setrecursionlimit(10**9)
DP = [0]*(H+1)

for x in range(1,H+1):
    DP[x] = min(DP[max(x-a,0)] + b for a,b in M)

print(DP[H])
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    q = [deque(),deque()]
    q[0].append(0)
    for i in range(n):
        t = i & 1
        ai = a[i]
        while q[t]:
            p = q[t].pop()
            for j in range(n):
                if ai[j]:
                    j1 = 1 << j
                    if p & j1:
                        continue
                    q[t ^ 1].append(p | j1)
                    dp[p | j1] += dp[p]
                    if dp[p | j1] >= mod:
                        dp[p | j1] %= mod
    print(dp[-1])


    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    b = [0]
    for i in range(n):
        b += [x + 1 for x in b]
    # print(b)
    c = [1 << i for i in range(n)]
    for i in range(n1-1):
        p = b[i]
        ap = a[p]
        for j in range(n):
            if ap[j]:
                j1 = c[j]
                if i & j1:
                    continue
                dp[i|j1] += dp[i]


    print(dp[-1] % mod)


    return


#main
if __name__ == '__main__':
    solve()