Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc044/tasks/arc060_a

"""
import sys
from sys import stdin
from copy import copy, deepcopy
input = stdin.readline


def solve(N, A, cards):
    ans = 0
    cards.append(0)
    cards.sort()
    W = max(cards) * N

    # dp[j][k][s]: j番目までのカードをk枚使って合計をsにする組み合わせ
    dp = [[[0] * (W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0] = 1

    for j in range(1, N+1):
        card = cards[j]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s < card:
                    dp[j][k][s] = dp[j-1][k][s]
                else:
                    dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-card]

    for k in range(1, N+1):
        ans += dp[N][k][k*A]
    return ans


def main(args):
    N, A = map(int, input().split())
    cards = [int(x) for x in input().split()]
    ans = solve(N, A, cards)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc044/tasks/arc060_a

"""
import sys
from sys import stdin
input = stdin.readline


def solve(N, A, cards):
    ans = 0
    cards.append(0)
    cards.sort()
    W = sum(cards)

    # dp[j][k][s]: j番目までのカードをk枚使って合計をsにする組み合わせ
    dp = [[[0] * (W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0] = 1

    for j in range(1, N+1):
        card = cards[j]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s < card:
                    dp[j][k][s] = dp[j-1][k][s]
                else:
                    dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-card]

    for k in range(1, N+1):
        if k*A <= W:
            ans += dp[N][k][k*A]
    return ans


def main(args):
    N, A = map(int, input().split())
    cards = [int(x) for x in input().split()]
    ans = solve(N, A, cards)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
s=(H-h)*(W-w)
print(s)


### FIXED CODE ###

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

print((H-h)*(W-w))
s, c = map(int, input().split())
ans = 0

if s<=2*c:
    c -= 2*s
    ans += s + c//4
else:
    ans += s

print (ans)


### FIXED CODE ###

n = int(input())
print (n * 800 - (n // 15) * 200)
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

for i in range(N):  a[i] -= K
dp = [[0 for _ in range(5020)] for _ in range(N + 5)]
dp[0][2500] = 1
for i in range(N):
    for j in range(5000):
        if j - a[i] >= 0:  dp[i + 1][j] += dp[i][j - a[i]]
        dp[i + 1][j] += dp[i][j] 
        
ans = dp[N][2500] - 1
print(ans)

### FIXED CODE ###

N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

for i in range(N):  a[i] -= K
dp = [[0 for _ in range(5500)] for _ in range(N + 5)]
dp[0][2500] = 1
for i in range(N):
    for j in range(5010):
        if j - a[i] >= 0 :  dp[i + 1][j] += dp[i][j - a[i]]
        dp[i + 1][j] += dp[i][j] 
        
ans = dp[N][2500] - 1
print(ans)
import itertools
import collections
import numpy as np

N=int(input())
S=list(input())
answer=0
col = collections.Counter(S)
values, counts = zip(*col.most_common())

for i in range(N):
    C=list(itertools.combinations(counts, i+1))
    kumiawase=[np.prod(j) for j in C]
    answer=(answer+sum(kumiawase))%(7+10**9)
print(answer)

### FIXED CODE ###

N=list(range(int(input())))
S=list(input())
S=sorted(S)
answer=0

prev=S[0]
counts = []
counter=0

for k in S:
    if k==prev:
        counter+=1
    else:
        prev=k
        if counter!=0:
            counts.append(1+counter)
        counter=1
if counter!=0:
    counts.append(1+counter)

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

answer=soujou(counts)-1
print(answer%(7+10**9))
import math

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Segment():
    def __init__(self, x1, y1, x2, y2):
        self.p1 = Point(x1, y1)
        self.p2 = Point(x2, y2)
        self.slope = None
        self.intersept = None
        if self.p1.x == self.p2.x:
            self.slope = float('inf')
        else:
            self.slope = (self.p2.y - self.p1.y)/(self.p2.x - self.p1.x)
            self.intersept = self.p1.y - self.slope*self.p1.x

    def is_in_range(self, x, y):
        return ((x - self.p1.x)*(x - self.p2.x) <= 0 and (y - self.p1.y)*(y - self.p2.y) <= 0)

    def is_intersect(self, seg):
        if self.slope == seg.slope: return False
        slope_diff = seg.slope - self.slope
        if self.slope == float('inf'):
            x = self.p1.x
        elif seg.slope == float('inf'):
            x = seg.p1.x
        else:
            x = -(seg.intersept - self.intersept)/slope_diff
        y = self.slope * x + self.intersept
        if seg.is_in_range(x, y) and self.is_in_range(x, y): return True
        return False


q = int(input())
for i in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = list(map(int, input().split(' ')))
    line1, line2 = Segment(x0, y0, x1, y1), Segment(x2, y2, x3, y3)
    if line1.is_intersect(line2):
        print(1)
    else:
        print(0)


### FIXED CODE ###

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Segment():
    def __init__(self, x1, y1, x2, y2):
        self.p1 = Point(x1, y1)
        self.p2 = Point(x2, y2)
        self.slope = None
        if self.p1.x == self.p2.x:
            self.slope = float('inf')
        else:
            self.slope = (self.p2.y - self.p1.y)/(self.p2.x - self.p1.x)

    def is_intersect(self, seg):
        a = (seg.p1.x - seg.p2.x) * (self.p1.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p1.x)
        b = (seg.p1.x - seg.p2.x) * (self.p2.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p2.x)
        c = (self.p1.x - self.p2.x) * (seg.p1.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p1.x)
        d = (self.p1.x - self.p2.x) * (seg.p2.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p2.x)
        e = (self.p1.x - seg.p1.x)*(self.p2.x - seg.p2.x)
        f = (self.p1.x - seg.p2.x)*(self.p2.x - seg.p1.x)
        g = (self.p1.y - seg.p1.y)*(self.p2.y - seg.p2.y)
        h = (self.p1.y - seg.p2.y)*(self.p2.y - seg.p1.y)
        return a*b <= 0 and c*d <= 0 and (e <= 0 or f <= 0) and (g <= 0 or h <= 0)

q = int(input())
for i in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = list(map(int, input().split(' ')))
    line1, line2 = Segment(x0, y0, x1, y1), Segment(x2, y2, x3, y3)
    if line1.is_intersect(line2):
        print(1)
    else:
        print(0)
n, k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
d=sorted([a.count(i) for i in set(a)])[::-1]
ans=0
for i in range(k):
  ans+=d[i]
print(n-ans)


### FIXED CODE ###

n, k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
d={i:0 for i in set(a)}
for i in a: d[i]+=1
print(n-sum([t[1] for t in sorted(d.items(), key=lambda x:-x[1])][:k]))
N=int(input())
A=list(map(int,input().split()))
def binbin(a):
    return int(bin(a).split("b")[1])
arr=[A[-1]]
arr.extend(A)
arr.append(A[0])
ans=[]
for i in range(1,N+1):
    ans.append(int(binbin(arr[i])) == int("".join(list(map(lambda x:str(int(x)%2),str(binbin(arr[i-1])+binbin(arr[i+1])))))))

if all(ans):
    if any(ans)==False:
        print("Yes")
else:
    if any(ans)==False:
    print("No")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=1
for i in A:
    a^=i
print(["No","Yes"][a==1])
print(' ',swapcase(1200))

### FIXED CODE ###

s = input()
print(s.swapcase())
"""
E.
"""
from functools import reduce
from collections import deque


def prod(x, y):
    return x * y % MOD

    
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
# abs_a_list = sorted(a_list, key=abs, reverse=True)
MOD = 10**9 + 7

if K%2 == 1:
    flg = True
    for a in a_list:
        if a >= 0:
            flg = False
            break
    if flg:
        print(reduce(prod, a_list[:K]))
        exit()

S = []
i = 0
a_list = deque(a_list)
while i < K:
    if a_list[0]*a_list[1] >= a_list[-1]*a_list[-2]:
        S.append(a_list.popleft())
        i += 1
    elif a_list[0]*a_list[1] < a_list[-1]*a_list[-2] and i <= K-2:
        S.append(a_list.pop())
        S.append(a_list.pop())
        i += 2
    else:
        S.append(a_list.popleft())
        i += 1

ans = reduce(prod, S)
print(ans)

### FIXED CODE ###

"""
E.
"""
from functools import reduce
from collections import deque


def prod(x, y):
    return x * y % MOD

    
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
# abs_a_list = sorted(a_list, key=abs, reverse=True)
MOD = 10**9 + 7

if K%2 == 1:
    flg = True
    for a in a_list:
        if a >= 0:
            flg = False
            break
    if flg:
        print(reduce(prod, a_list[:K]))
        exit()

S = []
a_list = deque(a_list)
i = 0
while i < K:
    if len(a_list)>=2:
        if a_list[0]*a_list[1] > a_list[-1]*a_list[-2]:
            S.append(a_list.popleft())
            i += 1
        elif a_list[0]*a_list[1] <= a_list[-1]*a_list[-2] and i <= K-2:
            S.append(a_list.pop())
            S.append(a_list.pop())
            i += 2
        else:
            S.append(a_list.popleft())
            i += 1
    else:
        S.append(a_list.popleft())
        i += 1
        
ans = reduce(prod, S)
print(ans)
import sys

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

newV=[]
for i in range(1,N+1):
    if not (V[i]>cummax[i-1] and cummin[i+1]>V[i]):
        newV.append(V[i])

V=newV
N=len(V)
all=pow(2,N,mod)
highid,lowid=-1,-1
Vmax=cummax[-2]
Vmin=cummin[1]
for i in range(0,N):
    if V[i]==Vmax:
        highid=i+1
    elif V[i]==Vmin:
        lowid=i+1
high=pow(2,highid-1,mod)
low=pow(2,N-lowid,mod)
if highid>lowid:
    highlow=pow(2,N+1-highid-lowid,mod)
else:
    highlow=1
ans=all+highlow-high-low
print(ans%mod)


### FIXED CODE ###

class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10**9+7
inv=pow(2,mod-2,mod)

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))

_const=[]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        _const.append((L,R))

const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))


M=len(const)
const=[(-10**15,0)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    l,r=const[id]
    l=max(l,Rconst[id-1]+1)
    res+=dp[id-1]*(pow(2,r-L+1,mod)-1)*pow(2,L-l,mod)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1
ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)
import math

N = int(input())
A = [int(x) for x in input().split()]

gcd = A[0]
for i in range(N):
    gcd = gcd * A[i] // math.gcd(gcd, A[i])

ans = 0
for j in range(N):
    ans += gcd / A[j]

print(int(ans % (10**9 +7)))

### FIXED CODE ###

from fractions import gcd
from functools import reduce
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=reduce(lambda x,y:x//gcd(x,y)*y,a)
ans=sum(map(lambda x:l//x,a))
print(ans%mod)
import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = list(map(int, readline().split()))

visited = [False] * n
visited[0] = True
l = [1]
while True:
    x = A[l[-1]-1]
    if visited[x-1]:
        break
    l.append(x)
    visited[x-1] = True
# print(x)
print(l[x-1:][(k-l.index(x)) % len(l[x-1:])])


### FIXED CODE ###

import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = list(map(int, readline().split()))

visited = [False] * n
visited[0] = True
l = [1]
while True:
    x = A[l[-1]-1]
    if visited[x-1]:
        break
    l.append(x)
    visited[x-1] = True
# print(l[l.index(x):])
if len(l) > k:
    print(l[k])
else:
    print(l[l.index(x):][(k-l.index(x)) % len(l[l.index(x):])])
N,k=map(int,input().split())
ans=0
for i in range(1,N+1):
  cnt=0
  while i < k:
    frag*(1/2)
    cnt+=1
    i*=2
  ans += (1/N)*i*(1/2)**cnt
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
cnt = 0
for i in range(1, N+1):
	tmp = i
	x = 0
	while tmp < K:
		tmp *= 2
		x += 1
	cnt += (1 / N) * (0.5 ** x)
print(cnt)
#include <list>
#include <string>
using namespace std;
#define ll long long
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string com;
    int key;
    list<ll> lst;
    list<ll>::iterator it,i=lst.end();
    while(n--){
        cin>>com;
        if(com=="insert"){
            cin>>key;
            lst.push_front(key);
        }
        else if(com=="delete"){
            cin>>key;
            for(it=lst.begin();it!=i;it++){
                if(*it==key){
                    lst.erase(it);
                    break;
                }
            }
        }
        else if(com=="deleteFirst") lst.pop_front();
        else                        lst.pop_back();
         
    }
    i--;
    for(it=lst.begin();it!=i;it++)  cout<<*it<<" ";
    cout<<*i<<"\n";
    return 0;
}



### FIXED CODE ###


import sys
     
A=[]
fp =0
bp =0
 
n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1
 
for e in A[bp:fp+1][::-1]:
    print int(e),
from sys import stdin
N,Y = [int(x) for x in stdin.readline().rstrip().split()]
flag = False
for x in range(N+1):
    for y in range(N+1):
        z = N - x - y
        if Y == 10000 * x + 5000 * y + 1000 * z:
            flag = True
            break
    else:
        continue
    break
if flag:
    print(x,y,z)
else:
    print(-1,-1,-1)

### FIXED CODE ###

from sys import stdin
S = (stdin.readline().rstrip())
S = "2018" + S[4:]
print(S)
N = input()

if N  == 1:
  print("Hello World")
else:
  a = input()
  b = input()
  print(a + b)

### FIXED CODE ###

N = int(input())

if N  == 1:
  print("Hello World")
else:
  a = int(input())
  b = int(input())
  print(str(a + b))
N = int(input())
S = input()
tmp = S[1]
ret = tmp
for i in S:
  if tmp == i:
    tmp = i
  else:
    ret += i
    tmp = i
print(len(ret))

### FIXED CODE ###

N = int(input())
S = input()
tmp = S[0]
ret = tmp
for i in S:
  if tmp == i:
    tmp = i
  else:
    ret += i
    tmp = i
print(len(ret))
N,P=map(int,input().split())
A=list(map(int,input().split()))
odd=0
for i in range(N):
  if A[i]%2==1: odd+=1
    break
if odd==0:
  if P==1: print(0)
  else: print(2**N)
else:
  print(2**(N-1))

### FIXED CODE ###

N,P=map(int,input().split())
A=list(map(int,input().split()))
odd=0
for i in range(N):
  if A[i]%2==1: odd+=1
if odd==0:
  if P==1: print(0)
  else: print(2**N)
else:
  print(2**(N-1))
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    S = stdin.readline().rstrip()
    count = 0
    for i in range(1000):
        left = 0
        not_found = False
        for c in f'{i:03}':
            for j in range(left, N):
                if S[j] == c:
                    left = j + 1
                    break
            else:
                not_found = True
                break
            if not_found:
                break
        if not not_found:
            count += 1
    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    S = stdin.readline().rstrip()
    count = 0
    for i in range(1000):
        left = 0
        not_found = False
        for c in '{:03}'.format(i):
            for j in range(left, N):
                if S[j] == c:
                    left = j + 1
                    break
            else:
                not_found = True
                break
            if not_found:
                break
        if not not_found:
            count += 1
    print(count)


if __name__ == "__main__":
    main()
import math
import itertools

# a = 6
# b = 4
#
# print(math.gcd(a, b))
k = int(input())
kk = k + 1
ans = 0
for i in range(1, kk):
    # print(i)
    for ii in rangea(1, kk):
        # print(ii)
        for iii in range(1, kk):
            # print((i,ii,iii))
            gcd2 = math.gcd(ii, iii)
            gcd3 = math.gcd(i, gcd2)
            ans += gcd3

print(ans)


### FIXED CODE ###

import math
import itertools

# a = 6
# b = 4
#
# print(math.gcd(a, b))
k = int(input())
kk = k + 1
ans = 0
for i in range(1, kk):
    # print(i)
    for ii in range(1, kk):
        # print(ii)
        for iii in range(1, kk):
            # print((i,ii,iii))
            gcd2 = math.gcd(ii, iii)
            gcd3 = math.gcd(i, gcd2)
            ans += gcd3

print(ans)
n,q=map(int,input().split())
l=[[] for _ in range(n)]
f=lambda x:int(x)-1
 
for i in range(n-1):
  a,b=map(f,input().split())
  l[a].append(b)
  l[b].append(a)
 
score=[0]*n
for j in range(q):
  p,x=map(int,input().split())
  score[p-1]+=x
 
visit=set()
def dfs(now):
  visit.add(now)
  for t in l[now]:
    if t not in visit:
      visit.add(t)
      score[t]+=score[now]
      dfs(t)
dfs(0)
print(*score)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
root=[[] for _ in range(n)]
f=lambda x:int(x)-1
 
for i in range(n-1):
  a,b=map(f,input().split())
  root[a].append(b)
  root[b].append(a)
 
score=[0]*n
for j in range(q):
  p,x=map(int,input().split())
  score[p-1]+=x
 
visit = [False]*n
def dfs(now):
  visit[now] = True
  for go in root[now]:
    if visit[go]:
      continue
    score[go] += score[now]
    dfs(go)

dfs(0)
print(*score)
import sys
sys.setrecursionlimit(100)

n = input()
k = int(input())
m = {}


def doit(n, k):
    if len(n) == 0:
        return k == 0
    d = int(n[0])
    if (n, k) not in m:
        ret = 0
        for i in range(d + 1):
            if i == d:
                ret += doit(n[1:], k - 1 if i > 0 else k)
            else:
                ret += doit('9' * (len(n) - 1), k - 1 if i > 0 else k)
        m[(n, k)] = ret
    return m[(n, k)]


print(doit(n, k))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)

n = input()
k = int(input())
m = {}


def doit(n, k):
    if len(n) == 0:
        return k == 0
    d = int(n[0])
    if (n, k) not in m:
        ret = 0
        for i in range(d + 1):
            if i == d:
                ret += doit(n[1:], k - 1 if i > 0 else k)
            else:
                ret += doit('9' * (len(n) - 1), k - 1 if i > 0 else k)
        m[(n, k)] = ret
    return m[(n, k)]


print(doit(n, k))
a, b = map(int, input().split())
c = a%500
if b >= c:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a = int(input())
b = int(input())
if a%500 <= b:
  print("Yes")
else:
  print("No")
N,M = map(int,input().split())
s = [list(map(int,input().split())) for i in range(M)]
ans = 0
ans_list = [ 0 for i in range(M)]

if M == 0:
    print('0')

for i in range(M):
    ans_list[s[i][0]-1] = s[i][1]

for i in range(M):
    ans = ans * 10 + ans_list[i]

if len(str(ans)) == N:
    print(ans)
else:
    print('-1')

### FIXED CODE ###

import sys
N,M = map(int,input().split())
sc = [list(map(int,input().split())) for i in range(M)]

ans = ['-1'] * N

for i in range(M):
    if ans[sc[i][0]-1] == sc[i][1]:
        continue
    elif ans[sc[i][0]-1] == '-1':
        ans[sc[i][0]-1] = sc[i][1]
    else:
        print('-1')
        sys.exit()

if N >= 2:
    if ans[0] == '-1':
        ans[0] = 1
    elif ans[0] == 0:
        print('-1')
        sys.exit()
else:
    if ans[0] == '-1':
        print(0)
        sys.exit()

for i in range(N):
    if ans[i] == '-1':
        ans[i] = 0

real = 0
for i in ans:
    real = real * 10 + i

print(real)
MOD = 10**9 + 7

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[x].append(y)
    G[y].append(x)

dp = [[1]*2 for _ in range(N)]
def dfs(pos: int, par: int):
    # dp[pos][0] = 白または黒の積 (posが白の時)
    # dp[pos][1] = 白の積 (posが黒の時)
    all = 1
    only_whilte = 1
    for v in G[pos]:
        if v != par:
            tmp = dfs(v, pos)
            all *= sum(tmp)
            only_whilte *= tmp[0]
            all %= MOD
            only_whilte %= MOD
    return [all, only_whilte]

print(sum(dfs(0, 0)))

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**6)

MOD = 10**9 + 7

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[x].append(y)
    G[y].append(x)

def dfs(pos: int, par: int):
    # posが白の時 -> 子はなんでも良い
    # posが黒の時 -> 子は全て白
    white = 1
    black = 1
    for v in G[pos]:
        if v != par:
            tmp = dfs(v, pos)
            white *= sum(tmp)
            black *= tmp[0]
            white %= MOD
            black %= MOD
    return [white, black]  # [白, 黒]

print(sum(dfs(0, 0))%MOD)
d

### FIXED CODE ###

ls = {'A':'T','C':'G','T':'A','G':'C'}
print(ls[input()])
a,b,c=map(int, input.split())
count = 0
if a==b:
  count = count + 1
if b==c:
  count = count + 1
if c==a:
  count = count + 1
if count == 1:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c = map(int, input().split())
count = 0
if a==b:
  count = count + 1
if b==c:
  count = count + 1
if c==a:
  count = count + 1
if count == 1:
  print("Yes")
else:
  print("No")
w = input()
for i in w:
  if w.coount(i) % 2:
    print('No')
    exit()
print('Yes')

### FIXED CODE ###

w = input()
for i in w:
  if w.count(i) % 2:
    print('No')
    exit()
print('Yes')
s = input()
t = input()

count = 0
 
for i in range(s):
  if s[i] != t[0]:
    count += 1
    
 print(count)

### FIXED CODE ###

s = list(input())
t = list(input())
count = 0

for i in range(len(s)):
  if s[i] != t[i]:
    count += 1

print(count)