Harryxun/stf_run huggingface dataset:
num_price, digit_price, budget = map(int, input().split())
min_by_digit = {x: int('1'+'0'*x) * num_price + (x+1) * digit_price for x in range(0, 10)}

max_digit = 0
for i in range(0, 10):
    if min_by_digit[i] > budget:
        break
    else:
        max_digit = i+1

if max_digit == 0:
    print("0")
    exit(0)

if max_digit == 10:
    print("1000000000")
    exit(0)

least = int('1'+'0'*(max_digit-1))
ans = min((budget - (digit_price * max_digit)) // num_price, least*10-1)
print(ans)


### FIXED CODE ###

week = ["SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT", ""]
week.reverse()
day = input()
print(week.index(day))
a=[]
N = int(input())
for i in range(N):
    a.append(int(input().strip()))


def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

for i in range(len(a)-1):
    gcd(a[i],a[i+1])
    lcm=(a[i]*a[i+1])//gcd(a[i],a[i+1])

print(lcm)

### FIXED CODE ###

a=[]
N = int(input())
for i in range(N):
    a.append(int(input().strip()))


def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

if N!=1:
    for i in range(len(a)-1):
        pr=a[i]*a[i+1]
        lcm=pr//gcd(a[i],a[i+1])
        a[i+1]=lcm
else:
    lcm=a[0]

print(lcm)
from collections import defaultdict

links = defaultdict(set)
n, q = list(map(lambda x: int(x), input().split()))
for _ in range(n):
    t, u, v = list(map(lambda x: int(x), input().split()))
    if t == 0:
        links[min(u, v)].add(max(u, v))
        links[v].add(u)
        continue
    print('1') if max(u, v) in links[min(u, v)] else print('0')


### FIXED 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()}
 
      
n, q = list(map(lambda x: int(x), input().split()))
uf = UnionFind(n)
for _ in range(q):
    t, u, v = list(map(lambda x: int(x), input().split()))
#     print(uf.parent_indexes)
    if t == 0:
        uf.union(u, v)
        continue
    print('1') if uf.same(u, v) else print('0')
import numpy

def euclidean_algorithm(a, b):
    if a < b:
        tmp = b
        b = a
        a = tmp

    ｑ = a // b
    r = a % b
    while r != 0:
        a = b
        b = q
        q = a // b
        r = a % b
    
    return b


def main():
    a, b = map(int, input().split())

    # print(numpy.lcm(a, b)) # AtCoderでは使用不可

    #ユークリッド互除法(最大公約数)
    gcd = euclidean_algorithm(a, b)
 
    # 最小公倍数
    lcm = (a*b)//gcd
    print(lcm)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def euclidean_algorithm(a, b):
    if a < b:
        tmp = b
        b = a
        a = tmp

    ｑ = a // b
    r = a % b
    while r != 0:
        a = b
        b = r
        q = a // b
        r = a % b

    return b


def main():
    a, b = map(int, input().split())

    #ユークリッド互除法(最大公約数)
    gcd = euclidean_algorithm(a, b)

    # 最小公倍数
    lcm = (a*b)//gcd
    print(lcm)

if __name__ == "__main__":
    main()
import math
import numpy as np
n = int(input())
# 素因数分解
s = math.sqrt(n)
i = 2
f = np.zeros(n)
while i <= s:
    while n % i == 0:
        f[i-1] += 1
        n = n // i
    i += 1

ans = 0
for x in f:
    e = 0
    while x > 0:
        e += 1
        x -= e
    ans += e
print(ans)

### FIXED CODE ###

import math
import numpy as np
n = int(input())

s = math.sqrt(n)
i = 2
f = {}
while i <= s:
    while n % i == 0:
        f[i] = f.get(i,0)+1
        n = n // i
    i += 1

ans = 0
for x in f.values():
    e = 0
    cumsum = 0
    while e + cumsum + 1 <= x:
        e += 1
        cumsum += e
    ans += e
print(ans+(n>1))
n=int(input())
a = n / 1.08
if a-int(a) == 0.00:
      x = int(a)
else:
      x = int(a) + 1
v = int(x * 1.08)
if v == n:
  print(x)
else:
  print(":(")


### FIXED CODE ###

M1, D1 = map(int, input().split())
M2, D2 = map(int, input().split())

if D2-D1 == 1:
  print(0)
else:
  print(1)
#!/opt/local/bin/python
# coding: UTF-8
import math
a,b,C = [float(i) for i in raw_input().split()]
S = 0.5 * a * b * math.sin(math.pi * (C / 180))
L = a + b + math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.cos(math.pi * (C / 180))
H = 2 * S / a
print S,L,H

### FIXED CODE ###

#!/opt/local/bin/python
# coding: UTF-8
import math
a,b,C = [float(i) for i in raw_input().split()]
S = 0.5 * a * b * math.sin(math.pi * (C / 180))
L = a + b + math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.cos(math.pi * (C / 180)))
H = 2 * S / a
print S,L,H
def main():
  h,w = map(int,input().split())
  s = [input() for _ in range(h)]
  c = [[10**5]*w for _ in range(h)]
  #print(sum([i.count(".") for i in s]))
  
  def func(dh,dw,step):
    if dh<0 or dw<0 or dh>=h or dw>=w:
      return
    step += 1
    if s[dh][dw] == ".":
      if c[dh][dw] > step:
        c[dh][dw] = step
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
          func(dh+i,dw+j,step)
  
  func(0,0,0)
  if c[h-1][w-1] == 10**5:
    return -1
  else:
    return sum([i.count(".") for i in s])-c[h-1][w-1]

print(main())

### FIXED CODE ###

from collections import deque
def main():
  h,w = map(int,input().split())
  s = [input() for _ in range(h)]
  #print(sum([i.count(".") for i in s]))
  
  def bfs(st):
    que = deque([st])
    c = [[0]*w for _ in range(h)]
    while que:
      ph,pw = que.popleft()
      step = c[ph][pw] + 1
      for dh,dw in ((1,0),(0,1),(-1,0),(0,-1)):
        nh = ph+dh
        nw = pw+dw
        if nh<0 or nw<0 or nh>=h or nw>=w:
          continue
        if s[nh][nw]=="#" or c[nh][nw] != 0:
          continue
        c[nh][nw] = step
        if (nh,nw) == (h-1,w-1):
          return step
        que.append((nh,nw))
  
  result = bfs((0,0))
  if result:
    return sum([i.count(".") for i in s])-result-1
  else:
    return -1

print(main())
import math
from collections import deque


def main():
    s = list(input())
    k = int(input())
    lst = []
    cnt = 1
    flg = 0
    ans = 0
    prev = s[0]
    for i in range(1, len(s)):
        if prev == s[i]:
            cnt += 1
        else:
            lst.append(cnt)
            cnt = 1
            prev = s[i]
            flg = 1
    lst.append(cnt)
    if flg == 0:
        print(s * k // 2)
        return
    ans += sum(list(map(lambda x: x // 2, lst[1:len(lst)-1])))*k
    if s[-1] == s[0]:
        ans += (lst[0] + lst[-1]) // 2 * (k - 1)
        ans += lst[0] // 2 + lst[-1] // 2
    else:
        ans += (lst[0] // 2 + lst[-1] // 2) * k
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###



def main():
    s = list(input())
    k = int(input())
    lst = []
    cnt = 1
    flg = 0
    ans = 0
    prev = s[0]
    for i in range(1, len(s)):
        if prev == s[i]:
            cnt += 1
        else:
            lst.append(cnt)
            cnt = 1
            prev = s[i]
            flg = 1
    lst.append(cnt)
    if len(lst) == 1:
        ans = len(s) * k // 2
    else:
        ans += sum(list(map(lambda x: x // 2, lst[1:len(lst)-1]))) * k
        # for l in lst[1: len(lst) - 1]:
        #     ans += l // 2 * k
        if s[-1] == s[0]:
            ans += (lst[0] + lst[-1]) // 2 * (k - 1)
            ans += lst[0] // 2 + lst[-1] // 2
        else:
            ans += (lst[0] // 2 + lst[-1] // 2) * k
    print(ans)


if __name__ == "__main__":
    main()
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * (110000)
def find(x):
    if root[x] >= 0:
        r = find(x)
    root[x] = r
    return r

def unite(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        root[a] += root[b]
        root[b] = a
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * n
def find(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find(root[x])
        return root[x]
    

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x
        

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)

ans = len([i for i in root if i < 0]) - 1
print(ans)
import copy
n = int(input())
l = []
for i in range(n):
    a = str(input())
    if "." not in a:
        l.append(float(a))
    else:
        dot = a.index(".")
        if len(a)-dot-1 <= 4:
            l.append(float(a))
        else:
            flag = 1
            for j in range(dot+5,len(a)):
                if a[j] != "0":
                    flag = 0
            if flag: l.append(float(a)) 
n = len(l)
a = [int(l[i]*10**4) for i in range(n)]
memo = [[0,0] for _ in range(n)]
for i in range(n):
    t = a[i]
    while t%2 == 0:
        t //= 2
        memo[i][0] += 1
    while t%5 == 0:
        t //= 5
        memo[i][1] += 1
a.sort()
memo.sort()
mem2 = [[0]*9 for _ in range(9)]
p = 0
for i in range(n):
    if memo[i][0] >= 8 and memo[i][1] >= 8:
        p += 1
    else:
        mem2[memo[i][0]][memo[i][1]] += 1
mems = copy.deepcopy(mem2)


for i in range(8,-1,-1):
    for j in range(7,-1,-1):
        mems[i][j] += mems[i][j+1]
for i in range(7,-1,-1):
    for j in range(8,-1,-1):
        mems[i][j] += mems[i+1][j]

s = 0
for i in range(9):
    for j in range(9):
        if i >= 4 and j >= 4:
            s += mem2[i][j] * (mems[8-i][8-j]-1)
        else:
            s += mem2[i][j] * mems[8-i][8-j]
s = s//2
s += p*(p-1)//2+p*(n-p)
print(s)

### FIXED CODE ###

import copy
n = int(input())
def point_shift(s,i):
    p = s.index(".")
    tale = len(s[p+1:])
    if tale <= i:
        return int(s[:p]+s[p+1:].ljust(i,"0"))
    else:
        return int(s[:p]+s[p+1:p+i+1])

a = []
for i in range(n):
    s = input()
    if "." not in s:
        a.append(int(s)*10**9)
    else:
        a.append(point_shift(s,9))

memo = [[0,0] for _ in range(n)]
for i in range(n):
    t = a[i]
    while t%2 == 0:
        t //= 2
        memo[i][0] += 1
    while t%5 == 0:
        t //= 5
        memo[i][1] += 1

l0 = [[0]*100 for _  in range(100)]
for i in range(n):
    l0[memo[i][0]][memo[i][1]] += 1

l1 = copy.deepcopy(l0)
for i in range(100):
    for j in range(98,-1,-1):
        l1[i][j] += l1[i][j+1]
for i in range(98,-1,-1):
    for j in range(100):
        l1[i][j] += l1[i+1][j]


ans = 0
for i in range(100):
    for j in range(100):
        x0,y0 = i,j
        x1,y1 = max(0,18-x0),max(0,18-y0)
        if x0 >= 9 and y0 >= 9:
            ans += l0[x0][y0]*(l1[x1][y1]-1)
        else:
            ans += l0[x0][y0]*l1[x1][y1]
print(ans//2)
N = int(input())
arr = [int(n) for n in input().split()]

swap_cnt = 0
minj = 0
for i in range(0, N):
    minj = i
    for j in range(i + 1, N - 1):
        if A[j] < A[minj]
            minj = j
        arr[i], arr[minj] = arr[minj], arr[i]
        swap_cnt += 1 if i != minj else 0

print(' '.join(map(str, arr)))
print(swap_cnt)



### FIXED CODE ###

N = int(input())
arr = [int(n) for n in input().split()]

swap_cnt = 0
for i in range(0, N):
    minj = i
    for j in range(i, N):
        if arr[j] < arr[minj]:
            minj = j
    if (i != minj):
        arr[i], arr[minj] = arr[minj], arr[i]
        swap_cnt += 1

print(' '.join(map(str, arr)))
print(swap_cnt)
a,b = map(int,raw_input().split())
if s[a+1] == "-" and len(s.strip("-")) == len(s) - 1:
    print "Yes"
else: print "No"    



### FIXED CODE ###

a,b = map(int,raw_input().split())
valid = True
s = raw_input()
for ind in range(len(s)):
        if ind == a:
            if s[ind] != "-":
                valid = False
        else:
            if s[ind].isalpha() or s[ind] == "-":
                valid = False        
if valid: print "Yes"
else: print "No"
a,b,k = list(map(int, input().split()))
for i in range(a, min(a+k, b+1)):
  print(i)
for i in range(max(a+k,b-k+1),b+1):
  print(i)

### FIXED CODE ###

print("Yes"  if ''.join(sorted(list(input()))) == "abc" else "No")
A, B = map(int, raw_input().split())
if A > 9 or B > 9:
  print (-1)
else:
  print(A*B)

### FIXED CODE ###

A, B = map(int, input().split())
if A > 9 or B > 9:
  print (-1)
else:
  print(A*B)
import collections

n = int(input())

al = [int(l) for l in input().split()]

a = []
b = []
for i, x in enumerate(al):
    if i%2 == 0:
        a.append(x)
    else:
        b.append(x)

ac = collections.Counter(a).most_common()
bc = collections.Counter(b).most_common()

if ac[0][0] != bc[0][0]:
    print(n-ac[0][1]-bc[0][1])
else:
    if len(ac) >= 2 and ac[0][1] == ac[1][1]:
        print(n-ac[0][1]-bc[0][1])
    elif len(bc) >= 2 and bc[0][1] == bc[1][1]:
        print(n-ac[0][1]-bc[0][1])

    min_c = n//2

    if len(bc) >= 1:
        min_c = min(min_c, n-ac[0][1]-bc[1][1])
    min_c = min(min_c, n-ac[0][1])
    if len(ac) >= 1:
        min_c = min(min_c, n-ac[1][1]-bc[0][1])
    min_c = min(min_c, n-bc[0][1])
    if len(ac) >= 1 and len(bc) >= 1:
        min_c = min(min_c, n-bc[1][1]-ac[1][1])
    print(min_c)
    


### FIXED CODE ###

import collections

n = int(input())

al = [int(l) for l in input().split()]

a = []
b = []
for i, x in enumerate(al):
    if i%2 == 0:
        a.append(x)
    else:
        b.append(x)

ac = collections.Counter(a).most_common()
bc = collections.Counter(b).most_common()

if ac[0][0] != bc[0][0]:
    print(n-ac[0][1]-bc[0][1])
else:
    if len(ac) == 1 and len(bc) == 1:
        print(n-max(ac[0][1], bc[0][1]))
    elif len(ac) == 1:
        print(n-max(ac[0][1], ac[1][1]+bc[0][1]))
    elif len(ac) == 1:
        print(n-max(bc[0][1], ac[0][1]+bc[1][1]))
    else:
        print(n-max(ac[1][1]+bc[0][1], ac[0][1]+bc[1][1]))
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect
import itertools


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    N = int(inputs[0])
    SSSS = 1000000007
    count = collections.Counter()

    for i in range(1, N+1):
        target = i
        is_end = False
        while not is_end:
            is_end = True
            for j in range(2, int(math.sqrt(target)+1)):
                if target % j == 0:
                    count[j] += 1
                    target = target // j
                    is_end = False
                    break
            if is_end and target != 1:
                count[target] += 1
    c = 1
    for k, v in count.items():
        c *= (v + 1)
        c = c % SSSS
    return c


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N-1))
    for r in ret:
        print(r)


### FIXED CODE ###

import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect
import itertools


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    N = int(inputs[0])
    SSSS = 1000000007
    count = collections.Counter()

    for i in range(1, N+1):
        target = i
        is_end = False
        while not is_end:
            is_end = True
            for j in range(2, int(math.sqrt(target)+1)):
                if target % j == 0:
                    count[j] += 1
                    target = target // j
                    is_end = False
                    break
            if is_end and target != 1:
                count[target] += 1
    c = 1
    for k, v in count.items():
        c *= (v + 1)
        c = c % SSSS
    return c


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)
n = input()
s = list(input())

sb = s.copy()

ans = 0

for i in range(len(s)-1):
	if(s[i] == "#" and s[i+1] == "."):
		if(i == 0):
			s[i] = "."
		elif(i > 0 and s[i-1] != "#"):
			s[i] = "."
		else:
			s[i+1] = "#"
		ans += 1

ansb = 0
for i in range(len(sb)-1):
	if(i == 0 and sb[i] != "."):
		sb[i] = "."
		ansb += 1
	elif(sb[i] == "#" and sb[i+1] == "."):
		if(i > 0 and sb[i-1] != "#"):
			sb[i] = "."
		else:
			sb[i+1] = "#"
		ansb += 1

#print(s)
#print(sb)


#print(ans)
#print(ansb)

ans = min(ans, ansb)

print(ans)

### FIXED CODE ###

n = input()
s = list(input())
 
ans = len(s)

sharp = 0
dot = 0
for string in s:
	if(string == "#"):
		sharp += 1
	else:
		dot += 1 

left_sharp = 0
right_dot = dot

for i in range(len(s)):
	temp_ans = left_sharp + right_dot
	ans = min(ans,temp_ans)
	if(s[i] == "."):
		right_dot -= 1
	else:
		left_sharp += 1

ans = min(ans, len(s) - dot) 

print(ans)
s=input()
if len(set(s))==2 and s.count(s[0])==2:
  print("Yes")
else:
  print("No)

### FIXED CODE ###

s=input()
if len(set(s))==2 and list(s).count(s[0])==2:
  print("Yes")
else:
  print("No")
s = input()
i = input()
print("YES" if s==t[::-1] else "NO")

### FIXED CODE ###

s = input()
t = input()
print("YES" if s==t[::-1] else "NO")
import functools
import operator
n = int(input())
a = list(map(int,input().split()))
c = functools.reduce(operator.mul,a)
if c > 10**18:
    print(-1)
else:
    print(c)

### FIXED CODE ###

from decimal import Decimal
a,b = input().split()
a=int(a)
b=Decimal(str(b))
c = a*b

print(int(c))
import math
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
B, R = K, N - K


def f(n):
    return math.factorial(n)


for i in range(K):
    print(f(R + 1) // f(R - i) // f(i + 1)
          * (f(B - 1) // f(B - i - 1) // f(i)) % MOD)


### FIXED CODE ###

import math
MOD = 10 ** 9 + 7

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


def f(n):
    return math.factorial(n)


for i in range(K):
    if N - K - i >= 0:
        print(f(N - K + 1) // f(N - K - i) // f(i + 1)
              * (f(K - 1) // f(K - i - 1) // f(i)) % MOD)
    else:
        print(0)
from statistics import mean

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

target = round(mean(a))
cost = 0
for num in a:
    cost += (num - target)**2

print(cost)


### FIXED CODE ###

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


def mean(numbers):
    return sum(a) / N


target = round(mean(a))
cost = 0
for num in a:
    cost += (num - target)**2

print(cost)
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N,M = [int(i) for i in input().strip().split()]
    students = [[int(i) for i in input().strip().split()] for _ in range(N)]
    checkpoints = [[int(i) for i in input().strip().split()] for _ in range(N)]
    ans = [0] * N

    for i,student in enumerate(students):
        dist = [float("inf")] * M
        for j, checkpoint in enumerate(checkpoints):
            dist[j] = abs(student[0] - checkpoint[0]) + abs(student[1] - checkpoint[1])
        ans[i] = dist.index(min(dist)) + 1

    return ans


if __name__ == "__main__":
    for n in main():
        print(n)


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N,M = [int(i) for i in input().strip().split()]
    students = [[int(i) for i in input().strip().split()] for _ in range(N)]
    checkpoints = [[int(i) for i in input().strip().split()] for _ in range(M)]
    ans = [0] * N

    for i,student in enumerate(students):
        dist = [float("inf")] * M
        for j, checkpoint in enumerate(checkpoints):
            dist[j] = abs(student[0] - checkpoint[0]) + abs(student[1] - checkpoint[1])
        ans[i] = dist.index(min(dist)) + 1

    return ans


if __name__ == "__main__":
    for n in main():
        print(n)
Created on Sun Sep 29 22:57:46 2019

@author: hiros
"""
import numpy as np

N = int(input())
A = list(map(int,input().split()))

ans = np.zeros(N)

for i in range(N):
    ans[A[i]-1] = i+1

for i in range(N):
    print(int(ans[i]), sep=' ', end=' ')

### FIXED CODE ###

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

for i in range(N-1):
    ans.append(0)

for i in range(N):
    ans[A[i]-1] = i+1

for i in range(N):
    print(int(ans[i]), end=' ')
a,b = map(int,input().split())
if a > 9 or b > 9:
    print(-1)
else:
    print(A*B)


### FIXED CODE ###

a,b = map(int,input().split())
if a > 9 or b > 9:
    print(-1)
else:
    print(a*b)
a = input()
d = 0
for x in range(a):
    b ,c = map(int,input().split())
    d = c-b+1
print(d)

### FIXED CODE ###

a =int( input())
d = 0

for x in range(a):
    b ,c = map(int,input().split())
    d += c-b+1
print(d)
from collections import defaultdict,Counter
n = int(input())
al = list(map(int, input().split()))

c_al  = Counter(al)

if n % 2 == 0 and 0 not in c_al.values():
    print(int(2**(n/2))%((10**9) + 7))
elif n % 2 != 0 and c_al[0] == 1:
    print(int(2 ** (n // 2))%((10**9) + 7))
else:
    print(0)

### FIXED CODE ###

from collections import Counter

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

c_al = Counter(al)

if n % 2 == 0:
    for k,v in c_al.items():
        if v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))

elif n % 2 != 0:
    for k, v in c_al.items():
        if k == 0:
            if v != 1:
                print(0)
                exit()
        elif v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))
#AGC007 A
'''
問題
縦H行で横W列の盤面がある
コマははじめ左上隅のマスに置かれており，右下隅に移動した
駒は1マスずつ上下左右に動ける
駒が通ったことのあるマスが提示されるので，駒が常に右または下にしか動いていなかったどうか判定せよ
ただし通ったことのあるマスは'#',一度も通らなかったマスは'.'で与えられる

考察
各行0,1,...,i,...,H-1に対して'#'のマスが存在する範囲を[ai,bi]とする。ただし0<=ai<=bi<=W-1
このとき各0,1,...,j,...,H-2について b_j == a_(j+1) であればよい
'''

import re

H,W = map(int,input().split(' '))
A = []

ans = ''
answers = ('Possible','Impossible')

r = re.compile(r'\.*#+\.*')

for i in range(H):
	s = input()
	#'#'が2箇所以上にわかれていたらその時点でアウト
	if len(r.findall(s)) == 1:
		A.append(s)
	else:
		ans = answers[1]
		break
		
for i in range(H-1):
	if A[i].rfind('#') == A[i+1].find('#'):
		continue
	else:
		ans = answers[1]
		break

if ans == '':
	ans = answers[0]

print(ans)

### FIXED CODE ###

#AGC007 A
'''
問題
縦H行で横W列の盤面がある
コマははじめ左上隅のマスに置かれており，右下隅に移動した
駒は1マスずつ上下左右に動ける
駒が通ったことのあるマスが提示されるので，駒が常に右または下にしか動いていなかったどうか判定せよ
ただし通ったことのあるマスは'#',一度も通らなかったマスは'.'で与えられる

考察
各行0,1,...,i,...,H-1に対して'#'のマスが存在する範囲を[ai,bi]とする。ただし0<=ai<=bi<=W-1
このとき各0,1,...,j,...,H-2について b_j == a_(j+1) であればよい
'''

import re

H,W = map(int,input().split(' '))
A = []

ans = ''
answers = ('Possible','Impossible')

r = re.compile(r'\.*#+\.*')

for i in range(H):
	s = input()
	if len(r.findall(s)) == 1:
		A.append(s)
	else:
		#'#'が2箇所以上にわかれていたらその時点でアウト
		ans = answers[1]
		break

if ans == '':
	for i in range(H-1):
		if A[i].rfind('#') == A[i+1].find('#'):
			continue
		else:
			ans = answers[1]
			break

if ans == '':
	ans = answers[0]

print(ans)
N, maxx, time = map(int, input.split())
ans = time * (N //maxx + 1)
if(N != 0): 
  	print(ans)
else 
	print("0")

### FIXED CODE ###

def multiplier(N,maxx,time):
  if N%maxx==0 :
    return N//maxx
  else :
    return N//maxx+1
  
def main():
	N,maxx,time = map(int, input().split())
	if N!=0 :
		ans = time * multiplier(N,maxx,time)
	else:
		ans=0  
	print(ans)
    
if __name__ == '__main__':
  main()
from fractions import gcd
from functools import reduce
n=int(input())
A=list(map(int,input().split()))
print(reduce(gcd, A)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
n=int(input())
A=list(map(int,input().split()))
print(reduce(gcd, A))
s = input()
if len(s)==set(s):
  print('yes')
else:
  print('no)

### FIXED CODE ###

s = input()
if len(s)==len(set(s)):
  print('yes')
else:
  print('no')