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

#!/usr/bin/env python3

import sys

debug = False

def solve(ds, n, x, m):
    ds = [d % m for d in ds]
    a_n = x + sum(ds[0:(n - 1) % len(ds)]) + ((n - 1) // len(ds) * sum(ds)) 
    cnt_same = ds[0:(n - 1) % len(ds)].count(0) + ((n - 1) // len(ds) * ds.count(0))
    cnt_decrease = a_n // m - x // m
    return n - 1 - cnt_decrease - cnt_same


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().split(sep)]


def dprint(*args, **kwargs):
    if debug:
        print(*args, **kwargs)
    return


def main():
    k, q = read_int_list()
    d = read_int_list()
    for _ in range(0, q):
        n, x, m = read_int_list()
        print(str(solve(d, n, x, m)))
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys

debug = False

def solve(ds, n, x, m):
    ds = [d % m for d in ds]

    nr_loop = (n - 1) // len(ds)
    lastloop_remaining = (n - 1) % len(ds)
    a_n = x
    cnt_zero = 0
    for i in range(0, len(ds)):
        dmod = ds[i] % m
        a_n += (dmod) * nr_loop
        if dmod == 0:
            cnt_zero += nr_loop
        if i < lastloop_remaining:
            a_n += dmod
            if dmod == 0:
                cnt_zero += 1
    cnt_decrease = a_n // m - x // m
    return n - 1 - cnt_decrease - cnt_zero


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().split(sep)]


def dprint(*args, **kwargs):
    if debug:
        print(*args, **kwargs)
    return


def main():
    k, q = read_int_list()
    d = read_int_list()
    for _ in range(0, q):
        n, x, m = read_int_list()
        print(str(solve(d, n, x, m)))
    

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

from collections import deque

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)
A = [0] * (n+1)
B = [0] * (n+1)
P = [0] * (q+1)
X = [0] * (q+1)
to = [[] for i in range(n+1)]
cnt = [0] * (n+1)
for i in range(1,n):
    A[i],B[i] = [int(j) for j in input().split()]
    to[A[i]].append(B[i])
    to[B[i]].append(A[i])
for i in range(1,q+1):
    P[i],X[i] = [int(j) for j in input().split()]
    T[P[i]] += X[i]
NIL = -1

q =deque()
q.append((1,0,NIL))
while len(q)>0:
    p,x,prev = q.pop()
    x += T[p]
    cnt[p] = x
    for i in to[p]:
        if i != prev:
            q.append((i,x,p))
for i in range(1,n+1):
    print(cnt[i] , end =" ")


### FIXED CODE ###

from collections import deque

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)

to = [[] for i in range(n+1)]
cnt = [0] * (n)
for i in range(1,n):
    a,b = [int(j) for j in input().split()]
    to[a].append(b)
    to[b].append(a)
for i in range(1,q+1):
    P,X = [int(j) for j in input().split()]
    T[P] += X
NIL = -1

q =deque()
q.append((1,0,NIL))
while len(q)>0:
    p,x,prev = q.pop()
    x += T[p]
    cnt[p-1] = x
    for i in to[p]:
        if i != prev:
            q.append((i,x,p))
print(*cnt)
### BUGGY CODE ###

import itertools
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0

def cmb(n, r):
    p = 10 ** 9 + 7
    M = 10 ** 6  
    fact = [1, 1]  
    factinv = [1, 1]
    inv = [0, 1]  
    for i in range(2, M + 1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

for i in range(N):
    fac = cmb(i, K-1) - cmb(N-i-1, K - 1)
    ans += fac*a[i]
print(ans%(10**9+7))

### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7
ans = 0
cmb = [0]*N
x = [0]*N
cmb[K-1] = 1
def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod
for i in range(1,N-K+1):
    x[i] = Pow(i, mod-2)
    
for i in range(K, N):
    cmb[i] = cmb[i-1]*i%mod*x[i-K+1]%mod
for i in range(N):
    fac = cmb[i] - cmb[N-i-1]
    num = fac*a[i]%mod
    ans += num
    ans = ans%(10**9+7)
print(ans)
### BUGGY CODE ###

#dame datta....
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = Counter(A)
    l = [0] * (10**6+1)
    for i in A:
        t = 2*i
        while t < 10**6 + 1:
            l[t] = 1
            t += i
    r = 0
    for i in A:
        if l[i] == 0 and a[i] == 1:
            r += 1
    return r
print(main())


### FIXED CODE ###

#dame datta....
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = sorted(A)
    a = Counter(A)
    l = [0] * (10**6+1)
    v = [0] * (10**6+1)
    for i in B:
        if v[i] == 1 or l[i] == 1:
            continue
        else:
            v[i] = 1
        t = 2*i
        while t < 10**6 + 1:
            l[t] = 1
            t += i
    r = 0
    for i in A:
        if l[i] == 0 and a[i] == 1:
            r += 1
    return r
print(main())
### BUGGY CODE ###

import math

k = int(input())

x = 0

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            x += math.gcd(math.gcd(a, b), c)
            
print(x)

### FIXED CODE ###

import math

k = int(input())

x = 0

for a in range(1, k+1):
    for b in range(1, k+1):
        t = math.gcd(a, b)
        for c in range(1, k+1):
            x += math.gcd(t, c)
            
print(x)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 個数制限なしナップサック問題
W,N = map(int,readline().split())

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

for i in range(N):
    w,v = map(int,readline().split())
    # dp[j] = 重さj以下でつくれる最大の価値
    for j in range(W+1):
        dp[j] = min(dp[j],dp[max(j-w,0)] + v)

print(dp[W])


### FIXED CODE ###

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

INF = 10**10
#print(magic)

AM = 0
for i in range(N):
    AM = max(AM,magic[i][0])
#print(AM)


dp = [INF for i in range(H+AM+1)]
dp[0] = 0

for i in range(1,H+AM+1):
    for j in range(N):
        if magic[j][0] > i:
            dp[i] = min(dp[i],magic[j][1])
        else:
            dp[i] = min(dp[i-magic[j][0]]+magic[j][1],dp[i])
ans = INF
for i in range(H,H+AM+1):
    ans = min(ans,dp[i])
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int,input().split()))
dp = [0]*N
for i in range(1,N):
  dp[i] = min([dp[j]+abs(H[i]-H[j]) for j in range(max(0,i-K),i)])
print(dp[-1])

### FIXED CODE ###

def main():
  n, k = map(int, input().split())
  h = [int(n) for n in input().split()]
  dp = [0]*n
  for i in range(1, n):
    dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i)])  
  print(dp[-1])

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

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    MOD = 998244353

    S = sum(A)
    a = A[0]
    # dp[i][j]: DP table for the number of one side length is j until i-th A[i].
    dp = [[0 for _ in range(S+1)] for _ in range(N)]
    dp[0][a] = 1
    dp[0][0] = 2

    # dp2[i][j]: DP table for the number of one side length is j and the other one is 0 until i-th A{i].
    dp2 = [[0 for _ in range(S+1)] for _ in range(N)]
    dp2[0][a] = 1
    dp2[0][0] = 1
    for i in range(1, N):
        a += A[i]
        for j in range(a+1):
            dp[i][j] = dp[i-1][j] * 2
            dp2[i][j] = dp2[i-1][j]

            if j >= A[i]:
                dp[i][j] += dp[i-1][j-A[i]]
                dp2[i][j] += dp2[i-1][j-A[i]]

            dp[i][j] %= MOD
            dp2[i][j] %= MOD

    ng = 0
    if S % 2 == 1:
        for i in range(S//2 + 1, S+1):
            ng += dp[N-1][i]

        ng = (ng * 3) % MOD

    else:
        for i in range(S//2, S+1):
            ng += dp[N-1][i]

        ng = (ng * 3 - dp2[N-1][S//2] * 3) % MOD

    ans = (pow(3, N, MOD) - ng) % MOD
    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    MOD = 998244353

    S = sum(A)
    a = A[0]
    # dp0[i][j]: DP table
    #            the number of combinations that the one side length is j 
    #            until using the i-th A[i].
    dp0 = np.zeros((N, S+1), dtype=np.int64)
    dp0[0, a] = 1
    dp0[0, 0] = 2

    # dp1[i][j]: DP table
    #            the number of one side length is j and the other one is 0
    #            until using the i-th A{i].
    dp1 = np.zeros((N, S+1), dtype=np.int64)
    dp1[0, a] = 1
    dp1[0, 0] = 1
    for i in range(1, N):
        a = A[i]

        dp0[i, :] += dp0[i-1, :] * 2
        dp0[i, a:] += dp0[i-1, :-a]
        dp0[i, :] %= MOD

        dp1[i, :] += dp1[i-1, :]
        dp1[i, a:] += dp1[i-1, :-a]
        dp1[i, :] %= MOD


    ng = 0
    if S % 2 == 1:
        ng = np.sum(dp0[N-1, S//2 + 1:])
        ng = (ng * 3) % MOD

    else:
        ng = np.sum(dp0[N-1, S//2:])
        ng = (ng * 3 - dp1[N-1][S//2] * 3) % MOD

    ans = (pow(3, N, MOD) - ng) % MOD
    return ans


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

n, m = map(int, input().split())
a = [int(input()) for x in range(m)]
mod = 10**9 + 7

l = [0]*(n+1)
l[0] = 1

for i in range(1, n+1):
  if i in a:
    if l[i-1] == 0:
      print(0)
      exit()
    else:
      l[i] = 0
  else:
    l[i] = (l[i-2] + l[i-1]) % mod

print(l[-1])


### FIXED CODE ###

n, m = map(int, input().split())
a = set([int(input()) for x in range(m)])

l = [0]*(n+1)
l[0] = 1

for i in range(1, n+1):
  if i in a:
    l[i] = 0
    continue
  else:
    l[i] = l[i-2] + l[i-1]

print(l[-1] % 1000000007)
### BUGGY CODE ###

N = raw_input()
N = int(N)

a = []
for i in range(N):
	s_input = raw_input()
	s_input = int(s_input)
	if s_input in a:
		a.remove(s_input)
	else:
		a.append(s_input)

print(len(a))

### FIXED CODE ###

n=int(raw_input())
li={}
while n !=0:
    a = raw_input()
    if a in li:
        del li[a]
    else:
        li[a]=a
    n-=1
print(len(li))
### BUGGY CODE ###

info = [int(i) for i in  input().split()]
t, a, k = info
for i in range(k):
    if t > 0:
        t -= 1
    elif a > 0:
        a -= 1
    else:
        break
print(t, a)

### FIXED CODE ###

info = [int(i) for i in  input().split()]
t, a, k = info
if t <= k:
    a = a - (k - t)
    t = 0
    if a <= 0:
        a = 0
else:
    t = t - k
print(t, a)
### BUGGY CODE ###

X = list(input())
now = 0
while now < len(X) - 1:
    if X[now] == 'S' and X[now + 1] == 'T':
        for _ in range(2):
            X.pop(now)
        now = max(0, now - 1)
    else:
        now += 1
print(len(X))

### FIXED CODE ###

from collections import deque
right = deque(input())
left = deque()
while right:
    left.append(right.popleft())
    if not right:
        break
    while left and right and left[-1] == 'S' and right[0] == 'T':
        left.pop()
        right.popleft()
print(len(left))
### BUGGY CODE ###

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

s=[[0]*W for i in range(H)]

for i in range(H):
    cnt = 0
    temp=input()

    for j in range(W):
        if temp[j]!="#":
            cnt+=1
        else:
            if j==0:
                continue
            else:
                for k in range(cnt):
                    s[i][j-(1+k)]=cnt
                cnt=0
    if cnt!=0:
        for k in range(cnt):
            s[i][W-1 - k] = cnt
        cnt = 0

ans=[]
mx=0
for i in range(W):
    cnt=0
    for j in range(H):
        if s[j][i]!=0:
            cnt+=1
            mx=max(mx,s[j][i])
        else:
            if j==0:
                continue
            else:
                ans.append(mx+cnt-1)
                cnt=0
                mx=0
    if cnt!=0:
        ans.append(mx+cnt-1)
        mx=0
print(max(ans))



### FIXED CODE ###

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

s=[[0]*W for i in range(H)]

for i in range(H):
    cnt = 0
    temp=input()

    for j in range(W):
        if temp[j]!="#":
            cnt+=1
        else:
            if j==0:
                continue
            else:
                for k in range(cnt):
                    s[i][j-(1+k)]=cnt
                cnt=0
    if cnt!=0:
        for k in range(cnt):
            s[i][W-1 - k] = cnt
        cnt = 0

ans=[]
mx=0
for i in range(W):
    cnt=0
    for j in range(H):
        if s[j][i]!=0:
            cnt+=1
            mx=max(mx,s[j][i])
        else:
            if j==0:
                continue
            else:
                ans.append(mx+cnt-1)
                cnt=0
                mx=0
    if cnt!=0:
        ans.append(mx+cnt-1)
        mx=0
print(max(ans))
### BUGGY CODE ###


n = int(input())
s = input()

ans = n
if s.count('#') == n or s.count('.') == n:
    ans = 0
    print(ans)
else:
    for i in range(n):
        num = s[:i].count('#') + s[i:].count('.')
        if num < ans:
            ans = num
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = list(input())
res = 10**9

cta = 0
ctb = 0
a = [0]*n
b = [0]*n
for i in range(n):
    if s[i] == '.':
        cta += 1
    else:
        ctb += 1
    a[i] = cta
    b[i] = ctb
for i in range(n):
    res = min(res,b[i]+a[-1]-a[i])
res = min(res,a[-1],b[-1])
print(res)
### BUGGY CODE ###

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())

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

List2=[list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N+1)

for i in range(M):
  a = List2[i][0]
  b = List2[i][1]  
  uf.union(a, b)
  
cnt = 0
for i in range(N):
  a = uf.find(List[i])
  b = uf.all_group_members()[a]
  if i+1 in b:
    cnt += 1
  
print(cnt)

### FIXED CODE ###

class UnionFindTree():
    
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
  
    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i]) 
            self.parent[i] = group
        return group
      
    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]: # rank is same
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px
                
            self.parent[py] = px
            self.size[px] += self.size[py]
    
    def getsize(self, x):
        return self.size[self.find(x)]
    
    def groups(self, index1=True):
        return set([self.find(i) for i in range(0+index1, N+index1)])
      
N,M = map(int,input().split())
List=list(map(int,input().split()))

List2=[list(map(int,input().split())) for i in range(M)]
uf = UnionFindTree(N+1)

for i in range(M):
  a = List2[i][0]
  b = List2[i][1]  
  uf.unite(a, b)
  
cnt = 0
for i,w in enumerate(List):
  if uf.find(i+1) == uf.find(w):
    cnt += 1
  
print(cnt)
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


N, K = map(int, input().split())
k_bitlen = K.bit_length()
dp = [[0] * N for _ in range(k_bitlen + 1)]
dp[0] = list(map(lambda x: int(x) - 1, input().split()))

for k in range(k_bitlen):
    for i in range(N):
        dp[k + 1][i] = dp[k][dp[k][i]]
pos = 0
for k in range(k_bitlen):
    if K >> k & 1:
        pos = dp[k][pos]
print(pos + 1)

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

pos = A[1]
path = [1]
visited = {1}
cycle_start = -1
for _ in range(N):
    if pos in visited:
        cycle_start = pos
        break
    visited.add(pos)
    path.append(pos)
    pos = A[pos]

if cycle_start > 0:
    cycle_start_idx = path.index(cycle_start)
    acyclic_path = path[:cycle_start_idx]
    cyclic_path = path[cycle_start_idx:]
    if K < len(acyclic_path):
        print(acyclic_path[K])
    else:
        print(cyclic_path[(K - len(acyclic_path)) % len(cyclic_path)])
else:
    print(path[K])
### BUGGY CODE ###

import numpy as np
H, W = map(int,input().split())
S = []
for h in range(H):
   S.append(input())
def calc(LR,RL,H,W,S):
   for h in range(H):
       for w in range(W):
           if S[h][w]==".":
               LR[h+1][w+1] = LR[h+1][w] + 1
           else:
               LR[h+1][w+1] = 0
           if S[h][W-w-1]==".":
               RL[h+1][W-w] = RL[h+1][W-w+1] + 1
           else:
               RL[h+1][W-w] = 0
   return LR, RL
LR = np.zeros((H+2,W+2)).astype(np.int)
RL = np.zeros((H+2,W+2)).astype(np.int)
UD = np.zeros((H+2,W+2)).astype(np.int)
DU = np.zeros((H+2,W+2)).astype(np.int)
LR, RL = calc(LR,RL,H,W,S)
S2 = ["" for i in range(len(S[0]))]
for i in range(len(S[0])):
   for j in range(len(S)):
       S2[i]+=(S[j][i])

UD, DU = calc(UD.T,DU.T,W,H,S2)
mx = 0
for h in range(H):
   for w in range(W):
       p = 0
       if (S[h][w]=="."):
           p = LR[h+1][w]+RL[h+1][w+2] + UD.T[h][w+1]+DU.T[h+2][w+1] + 1
           mx = max(mx,p)
print (mx)

### FIXED CODE ###

import numpy as np
H , W = list(map(int, input().split()))
S = np.array([list(input().rstrip()) for _ in range(H)]) == '.'
U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
for h in range(1, H):
    U[h] = (U[h - 1] + 1) * S[h - 1]
for h in reversed(range(H - 1)):
    D[h] = (D[h + 1] + 1) * S[h + 1]
for w in range(1, W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w - 1]
for w in reversed(range(W - 1)):
    R[:, w] = (R[:, w + 1] + 1) * S[:, w + 1]
print(np.max((U+D+L+R) * S) + 1)
### BUGGY CODE ###

def solve(V, G):
    for i in range(V):
        G[i][i] = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if G[i][k] + G[k][j] < G[i][j] < float("inf"):
                    return False, G
                elif G[i][j] == G[i][k] + G[k][j]:
                    G[i][j] = float("inf")
    return True, G


def dist(V, G):
    ans = 0
    for i in range(V):
        for j in range(i, V):
            if G[i][j] < float("inf"):
                ans += G[i][j]
    return ans


def main():
    V = int(input())
    G = [[int(i) for i in input().split()] for i in range(V)]
    flag, G = solve(V, G)
    if flag:
        print(dist(V, G))
    else:
        print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def solve(V, G):
    ans = 0
    for i in range(V - 1):
        for j in range(i + 1, V):
            direct = G[i][j]
            for k in range(V):
                if k == i or k == j:
                    continue
                ind = G[i][k] + G[k][j]
                if direct > ind:
                    return -1
                elif direct == ind:
                    break
            else:
                ans += direct
    return ans


def main():
    V = int(input())
    G = [[int(i) for i in input().split()] for i in range(V)]
    print(solve(V, G))


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

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

friends = []
blocks = []
groups = []
fs = [[] for _ in range(n+1)]
bs = [[] for _ in range(n+1)]

for _ in range(m):
    friends.append(tuple(map(int, input().split())))
for _ in range(k):
    blocks.append(tuple(map(int, input().split())))

for i, j in friends:
    fs[i].append(j)
    fs[j].append(i)

for i, j in blocks:
    bs[i].append(j)
    bs[j].append(i)

seen = [False]*(n+1)
while True:
    for i in range(1, n+1):
        if not seen[i]:
            stack = [i]
            break
    else:
        break
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        seen[node] = True
        for c_node in fs[node]:
            if seen[c_node]:
                continue
            stack.append(c_node)
    groups.append(tmp)


for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(fs[i]) - set(bs[i]))-1, end=' ')
            break

### FIXED CODE ###

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

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

for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)

for _ in range(k):
    c, d = map(int, input().split())
    blocks[c].append(d)
    blocks[d].append(c)

groups = [-1]*(n+1)
n_groups = []
g = 0
for i in range(1, n+1):
    if groups[i]>=0:
        continue
    stack = [i]
    cnt = 0
    groups[i] = g
    while len(stack)>0:
        node = stack.pop()
        for c_node in friends[node]:
            if groups[c_node]>=0:
                continue
            stack.append(c_node)
            groups[c_node] = g
            cnt += 1
    n_groups.append(cnt)
    g += 1

ans = []
for i in range(1, n+1):
    tmp = n_groups[groups[i]]
    for j in friends[i]:
        if groups[i] == groups[j]:
            tmp -= 1
    for j in blocks[i]:
        if groups[i] == groups[j]:
            tmp -= 1
    ans.append(tmp)

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

import math
K=200
ans=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            tempgcd=math.gcd(a,b)
            ans=ans+math.gcd(tempgcd,c)
print(ans)

### FIXED CODE ###

import math
K=int(input())
ans=0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            tempgcd=math.gcd(a,b)
            if a==b or b==c or a==c:
              if a==b and b==c:
                ans=ans+math.gcd(tempgcd,c)
              else:
                ans=ans+3*math.gcd(tempgcd,c)
            else:
              ans=ans+6*math.gcd(tempgcd,c)
            
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [0] + [int(a) for a in input().split()]
for i in range(N):
    A[i+1] += A[i]
S = []
for i in range(1, N+1):
    for j in range(i):
        S.append(A[i] - A[j])
l, r = 0, 1 << 50
while r - l > 1:
    m = (l+r) // 2
    if len([1 for i in range(len(S)) if S[i] & m == m]) >= K:
        l = m
    else:
        r = m
print(l)

### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + [int(a) for a in input().split()]
for i in range(N):
    A[i+1] += A[i]
S = []
for i in range(1, N+1):
    for j in range(i):
        S.append(A[i] - A[j])
l, r = 0, 1 << 50
while r - l > 1:
    m = (l+r) // 2
    if len([1 for i in range(len(S)) if S[i] & m == m]) >= K:
        l = m
    else:
        r = m
print(l)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = [np.flatnonzero(np.array(list(map(int, input().split())))) for _ in range(N)]

MOD = 10 ** 9 + 7
dp = np.zeros(1 << N, dtype=np.int64)
dp[0] = 1
for a in A:
    new_dp = np.zeros_like(dp)
    for i in a:
        x = (1 << i)
        new_dp[x:] += dp[:-x]
    dp = new_dp
    dp %= MOD
print(dp[-1])


### FIXED CODE ###

N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10 ** 9 + 7

dp = [0] * (1 << N)
dp[0] = 1
for b in range(1, 1 << N):
    i = bin(b).count('1')
    for x in range(N):
        if (b >> x) & 1 and A[i - 1][x]:
            dp[b] += dp[b ^ (1 << x)]
    dp[b] %= MOD
print(dp[-1])