A continued fraction of height n is a fraction of form $a_{1} + \frac{1}{a_{2} + \frac{1}{\ldots + \frac{1}{a_{n}}}}$. You are given two rational numbers, one is represented as [Image] and the other one is represented as a finite fraction of height n. Check if they are equal.


-----Input-----

The first line contains two space-separated integers p, q (1 ≤ q ≤ p ≤ 10^18) — the numerator and the denominator of the first fraction.

The second line contains integer n (1 ≤ n ≤ 90) — the height of the second fraction. The third line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^18) — the continued fraction.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Output-----

Print "YES" if these fractions are equal and "NO" otherwise.


-----Examples-----
Input
9 4
2
2 4

Output
YES

Input
9 4
3
2 3 1

Output
YES

Input
9 4
3
1 2 4

Output
NO



-----Note-----

In the first sample $2 + \frac{1}{4} = \frac{9}{4}$.

In the second sample $2 + \frac{1}{3 + \frac{1}{1}} = 2 + \frac{1}{4} = \frac{9}{4}$.

In the third sample $1 + \frac{1}{2 + \frac{1}{4}} = \frac{13}{9}$.

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3

from fractions import Fraction

def __starting_point():
    p, q = list(map(int, input().split()))
    n = int(input())
    l = list(map(int, input().split()))

    f = Fraction(l[-1], 1)

    for x in l[-2::-1]:
        f = 1 / f
        f += x

    print(["NO", "YES"][f == Fraction(p, q)])



__starting_point()

from  fractions import *
p,q  = map(int,input().split())
a1 = Fraction(p,q)
n = int(input())
aaa = list(map(int,input().split()))
d2 = Fraction(aaa[-1],1)
for i in range(2,n+1):
    d2 = 1/d2+aaa[-i]
#print (d2)
print("YES" if a1 == d2 else "NO")

from fractions import Fraction
pq = Fraction(*map(int, input().split()))
input()
a = list(map(int, input().split()))
a.reverse()
f = Fraction(a[0], 1)
for i in a[1:]:
  f = i + Fraction(1, f)
if pq == f:
  print("YES")
else:
  print("NO")

from fractions import*
from sys import*
from copy import*
from time import*


class Fraction:
    def __init__(self, x = 0, y = 1):
        if(type(x) == str):
            if x.find('/') != -1:
                a = list(map(int, x.split('/')))
            else:
                a = list(map(int, x.split()))
            self.num = a[0]
            if len(a) == 1:
                self.den = 1
            else:
                self.den = a[1]
        elif(type(x) == Fraction):
            self.num, self.den = x.num, x.den
        else:
            self.num, self.den = x, y
        self.reduce()

    def __str__(self):
        if self.den == 1:
            return str(int(self.num))
        return str(int(self.num)) + '/' + str(int(self.den))

    def reduce(self):
        d = gcd(abs(self.num), abs(self.den))
        if self.den < 0:
            self.den, self.num = -self.den, -self.num
        self.num, self.den = self.num // d, self.den // d

    def __lt__(self, other):
        if type(other) == Fraction:
            return self.num * other.den < other.num * self.den
        else:
            return self.num < self.den * other

    def __le__(self, other):
        if type(other) == Fraction:
            return self.num * other.den <= other.num * self.den
        else:
            return self.num <= self.den * other

    def __gt__(self, other):
        if type(other) == Fraction:
            return self.num * other.den > other.num * self.den
        else:
            return self.num > self.den * other

    def __ge__(self, other):
        if type(other) == Fraction:
            return self.num * other.den >= other.num * self.den
        else:
            return self.num >= self.den * other

    def __eq__(self, other):
        if type(other) == Fraction:
            return self.num * other.den == other.num * self.den
        else:
            return self.num == self.den * other

    def __ne__(self, other):
        if type(other) == Fraction:
            return self.num * other.den != other.num * self.den
        else:
            return self.num != self.den * other

    def __mul__(self, other):
        if(type(other) == float):
            return (self.num * other) / self.den
        elif type(other) == Poly:
            return NotImplemented
        else:
            other = Fraction(other)
            return Fraction(self.num * other.num, self.den * other.den)

    def rmul(self, other):
        return other * self

    def __rmul__(self, other):
        if(type(other) == float):
            return (self.num * other) / self.den
        else:
            other = Fraction(other)
            return Fraction(self.num * other.num, self.den * other.den)

    def __imul__(self, other):
        if(type(other) == float):
            self = (self.num * other) / self.den
        else:
            other = Fraction(other)
            self.num *= other.num
            self.den *= other.den
            self.reduce()
        return self

    def __truediv__(self, other):
        if(type(other) == float):
            return self.num / (self.den * other)
        else:
            other = Fraction(other)
            return self * Fraction(other.den, other.num)

    def __rtruediv__(self, other):
        if(type(self) == float):
            return other.num / (other.den * self)
        else:
            self = Fraction(self)
            return other * Fraction(self.den, self.num)

    def __itruediv__(self, other):
        if(type(other) == float):
            self = self.num / (self.den * other)
        else:
            other = Fraction(other)
            self = self * Fraction(other.den, other.num)
            self.reduce()
        return self

    def __pow__(self, other):
        if type(other) == Fraction:
            return (self.num / self.den) ** (other.num / other.den)
        elif type(other) == int:
            if other > 0:
                return Fraction(self.num ** other, self.den ** other)
            else:
                return 1 / Fraction(self.num ** (-other), self.den ** (-other))
        else:
            return (self.num / self.den) ** other

    def __rpow__(self, other):
        return other ** (self.num / self.den)

    def __ipow__(self, other):
        if other > 0:
            self.num **= other
            self.den **= other
        else:
            self.num **= (-other)
            self.den **= (-other)
            self.num, self.den = self.den, self.num
        return self

    def __add__(self, other):
        if type(other) == float:
            return self.num / self.den + other
        elif type(other) == Poly:
            return NotImplemented
        else:
            other = Fraction(other)
            return Fraction(self.num * other.den + other.num * self.den, self.den * other.den)

    def __radd__(self, other):
        return self + other

    def __iadd__(self, other):
        if type(other) == float:
            self = self.num / self.den + other
        else:
            other = Fraction(other)
            self.num = self.num * other.den + other.num * self.den
            self.den = self.den * other.den
            self.reduce()
        return self

    def __sub__(self, other):
        if type(other) == float:
            return self.num / self.den - other
        elif type(other) == Poly:
            return NotImplemented
        else:
            other = Fraction(other)
            return Fraction(self.num * other.den - other.num * self.den, self.den * other.den)

    def __rsub__(self, other):
        if(type(self - other) == Fraction):
            return Fraction(-(self - other).num, (self - other).den)
        else:
            return -(self - other)

    def __isub__(self, other):
        if type(other) == float:
            self = self.num / self.den - other
        else:
            other = Fraction(other)
            self.num = self.num * other.den - other.num * self.den
            self.den = self.den * other.den
            self.reduce()
        return self

    def __pos__(self):
        return self

    def __neg__(self):
        return Fraction(-self.num, self.den)

    def __abs__(self):
        return Fraction((-self.num) * int(self.num < 0) + (self.num) * (self.num >= 0), self.den)

    def __int__(self):
        return self.num // self.den

    def __float__(self):
        return self.num / self.den

    def __round__(self, x = 0):
        return round(float(self), x)


class Poly:
    def __init__(self, s = 0):
        if type(s) in [int, float, Fraction]:
            self.list = [s]
        elif type(s) == str:
            self.list, s = [], s.split()
            for elem in S:
                self.list += eval(elem)
        elif type(s) == Poly:
            self.list = s.list
        else:
            self.list = list(s)

    def __str__(self):
        P, S, power, first = [chr(8304), chr(185), chr(178), chr(179)] + [chr(i) for i in range(8308, 8314)], "", len(self.list) - 1, True
        for i in range(len(self.list) - 1, -1, -1):
            current = self.list[i]
            if current != 0:
                if current > 0:
                    S += " + " * int(not first)
                else:
                    S += " - " * int(not first) + "-" * int(first)
                current = abs(current)
                if current != 1 or (current == 1 and power == 0):
                    if type(current) == Fraction:
                        if current.den == 1:
                            S += str(int(current.num))
                        else:
                            S += "(" + str(current) + ")"
                    elif type(current) == float:
                        S += str(round(current, 3))
                    else:
                        S += str(current)
                S += ('x' * (power != 0))
                for elem in str(power):
                    S += P[int(elem)] * (not(elem in ["0", "1"] and len(str(power)) == 1))
                first = len(S) == 0
            power -= 1
        if S == "":
            return "0"
        return S

    def __neg__(self):
        result = []
        for elem in self.list:
            result.append(-elem)
        return Poly(result)

    def __add__(self, other):
        result = []
        if type(other) == Poly:
            for i in range(max(len(self.list), len(other.list))):
                if i < len(self.list):
                    if i < len(other.list):
                        result.append(self.list[i] + other.list[i])
                    else:
                        result.append(self.list[i])
                else:
                    if i < len(other.list):
                        result.append(other.list[i])
                    else:
                        result.append(0)
            return Poly(result)
        else:
            lolka = [self.list[0] + other] + self.list[1:]
            return Poly(lolka)

    def __radd__(self, other):
        return self + other

    def __iadd__(self, other):
        self.list = (self + other).list
        return self

    def __sub__(self, other):
        result = []
        if type(other) == Poly:
            for i in range(max(len(self.list), len(other.list))):
                if i < len(self.list):
                    if i < len(other.list):
                        result.append(self.list[i] - other.list[i])
                    else:
                        result.append(self.list[i])
                else:
                    if i < len(other.list):
                        result.append(-other.list[i])
                    else:
                        result.append(0)
            return Poly(result)
        else:
            lolka = [self.list[0] - other] + self.list[1:]
            return Poly(lolka)

    def __rsub__(self, other):
        return -(self - other)

    def __isub__(self, other):
        self.list = (self - other).list
        return self

    def __or__(self, other):
        if len(self.list) == 1:
            return self.list[0]
        result = self.list[len(self.list) - 1]
        for i in range(len(self.list) - 2, -1, -1):
            result = result * other + self.list[i]
        return result

    def __mul__(self, other):
        result, p = [], Poly(other)
        for i in range(len(self.list)):
            for j in range(len(p.list)):
                if len(result) > i + j:
                    result[i + j] += self.list[i] * p.list[j]
                else:
                    result += [0] * (i + j - len(result)) + [self.list[i] * p.list[j]]
        return Poly(result)

    def __rmul__(self, other):
        return self * other

    def __imul__(self, other):
        self.list = (self * other).list
        return self

    def __pow__(self, other):
        if other == 0:
            return Poly(1)
        if other % 2 == 1:
            return Poly((self ** (other - 1)) * self)
        else:
            lolka = self ** (other // 2)
            return Poly(lolka * lolka)

    def __ipow__(self, other):
        self.list = (self ** other).list
        return self

    def __divmod__(self, other):
        result = [0] * 100
        p = deepcopy(self.list)
        q = Poly(other).list
        power1, power2 = len(p) - 1, len(q) - 1
        while(power1 > -1 and p[power1] == 0):
            power1 -= 1
        while(power2 > -1 and q[power2] == 0):
            power2 -= 1
        while(power1 > -1 and power2 > -1 and power1 >= power2):
            minus = [0] * (power1 - power2)
            if type(p[power1]) == int and type(q[power2]) == int:
                if p[power1] % q[power2] == 0:
                    current = p[power1] // q[power2]
                else:
                    current = Fraction(p[power1], q[power2])
            else:
                current = p[power1] / q[power2]
            for elem in q:
                minus += [elem * current]
            for i in range(max(len(p), len(minus))):
                if i < len(p):
                    if i < len(minus):
                        p[i] -= minus[i]
                else:
                    if i < len(minus):
                        p.append(-minus[i])
                    else:
                        p.append(0)
            result[power1 - power2] = current
            while(power1 > -1 and p[power1] == 0):
                power1 -= 1
            while(power2 > -1 and q[power2] == 0):
                power2 -= 1
            #result += [current]
        return (Poly(result), Poly(p))

    def __rdivmod__(self, other):
        return  divmod(Poly(other), self)

    def __floordiv__(self, other):
        return divmod(self, other)[0]

    def __rfloordiv__(self, other):
        return divmod(Poly(other), self)[0]

    def __ifloordiv__(self, other):
        self.list = (divmod(self, other)[0]).list
        return self

    def __mod__(self, other):
        return divmod(self, other)[1]

    def __rmod__(self, other):
        return divmod(Poly(other), self)[1]

    def __imod__(self, other):
        self.list = (divmod(self, other)[1]).list
        return self

#begin = time()
p, q = list(map(int, input().split()))
lolka = Fraction(p, q)
n = int(input())
A = list(map(int, input().split()))
Answer = Fraction(A[-1])
for i in range(len(A) - 2, -1, -1):
    Answer = 1 / Answer
    Answer += A[i]
if(Answer == lolka):
    print("YES")
else:
    print("NO")
#print(time() - begin)



p,q=tuple(map(int,input().split()))
n1=input().split()
n=int(n1[0])
a=list(map(int,input().split()))
x=1
y=a[n-1]
for i in range (n-2,-1,-1):
   x1=a[i]*y+x
   x=y
   y=x1
if p*x==q*y:
   print('YES')
else:
   print('NO')
   


#!/usr/local/bin/python3.3 -tt

import fractions
import sys


def __starting_point():
    def _(f):
        for l in f:
            for i in l.split():
                yield int(i)

    g = _(sys.stdin)

    pq = fractions.Fraction(next(g), next(g))

    n, a = next(g), []

    for i in range(n):
        a.append(next(g))

    r = fractions.Fraction(a.pop())

    while a:
        r = fractions.Fraction(a.pop()) + fractions.Fraction(1, r)

    if r == pq:
        print("YES")
    else:
        print("NO")

__starting_point()

3

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

def red(pr):
	a, b = pr
	g = gcd(a, b)
	return (a // g, b // g)

def rev(pr):
	a, b = pr
	return (b, a)

def add(pr, i):
	a, b = pr
	a += b * i
	return red((a, b))

import sys
args = list(map(int, sys.stdin.read().split()))
p, q = args[0], args[1]
args = args[2:]
n = args[0]
args = args[1:]
a = args[::-1]
s = (a[0], 1)
a = a[1:]
for i in a:
	s = add(rev(s), i)
if red(s) == red((p, q)):
	print("YES")
else:
	print("NO")


import re
import itertools
from collections import Counter, deque
from fractions import gcd

class Task:
    p, q = 0, 0
    a = []
    answer = ''
	
    def getData(self):
        self.p, self.q = [int(x) for x in input().split(' ')]
        input()
        self.a = [int(x) for x in input().split(' ')]
        #inFile = open('input.txt', 'r')
        #inFile.readline().rstrip()
        #self.childs = inFile.readline().rstrip()

    def solve(self):
        p, q = self.toFraction(self.a)
        if self.p * q == self.q * p:
            self.answer = 'YES'
        else:
            self.answer = 'NO'

    def toFraction(self, a):
        if len(a) == 1:
            return a[0], 1
        q, p = self.toFraction(a[1 : ])
        d = gcd(a[0] * q + p, q)
        return (a[0] * q + p) // d, q // d

    def printAnswer(self):
        print(self.answer)
        #outFile = open('output.txt', 'w')
        #outFile.write(self.answer)

task = Task()
task.getData()
task.solve()
task.printAnswer()


3

p, q = tuple(map(int, input().strip().split()))
n = int(input().strip())
a = list(map(int, input().strip().split()))
a.reverse()

def gcd(a, b):
    while a:
        a, b = b % a, a
    return b

g = gcd(p, q)
p, q = p // g, q // g

u, v = 0, 1;

for i in a:
    v, u = v * i + u, v
    g = gcd(u, v)
    u, v = u // g, v // g
if p == v and q == u:
    print("YES")
else:
    print("NO")


import math
import sys

def gcd(x, y):
    if(y == 0):
        return x
    else:
        return gcd(y,x%y)
p, q = list(map(int,sys.stdin.readline().split()))
n = int(input())
a = [0] * n;
b = list(map(int,sys.stdin.readline().split()))
l = 0
for i in b: 
    a[l] = i
    l = l + 1
x, y = a[n-1], 1
for i in range(n-2,-1,-1):
    x, y = y, x
    x = x + y*a[i]
g1 = gcd(p,q)
g2 = gcd(x,y)
p = p // g1
q = q // g1
x = x // g2
y = y // g2
if(x == p and y == q):
    print("YES")
else:
    print("NO")


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

def red(frac):
    gcdfrac = gcd(frac[0],frac[1])
    return (frac[0] // gcdfrac, frac[1] // gcdfrac)

def add(i, frac):
    a,b = frac
    a += b * i
    return red((a,b))

import sys
args = list(map(int, sys.stdin.read().split()))
p, q = args[0], args[1]
n = args[2]
s = (args[2+n],1)
for i in range(0,n-1):
    s = add(args[1+n-i] , (s[1],s[0]))
if(s == red((p,q))):
    print('YES')
else:
    print('NO')

#!/usr/bin/env python
#coding:utf-8

from fractions import Fraction

def frac(lis,i):
    if i == len(lis)-1 :
        return lis[i]
    else:
        return lis[i]+1/frac(lis,i+1)

def main():
    linesp = input().split(" ")
    p,q = int(linesp[0]),int(linesp[1])
    one = Fraction(p,q)

    n = int(input())

    A = []
    for s in input().split(" "):
        A.append(Fraction(int(s)))

    two = frac(A,0)
    if one == two:
        print("YES")
    else:
        print("NO")

def __starting_point():
    main()

__starting_point()


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

p, q = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
g = gcd(p, q)
p = p // g
q = q // g
k = A[n - 1]
l = 1
for i in range(n - 2, -1, -1):
	k, l = l, k
	k += A[i] * l
	g = gcd(k, l)
	k = k // g
	l = l // g
if (k == p and q == l):
	print ("YES")
else:
	print ("NO")

P, Q = [int(x) for x in input().split()]

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

U, V = 1, 0
for x in A[::-1]:
    U, V = V, U
    U, V = V * x + U, V

if U * Q == P * V:
    print("YES")
else:
    print("NO")


from decimal import *
getcontext().prec = 75
p = input().split()

n = int(input())

c = input().split()





a='0'
for i in range(n-1,0,-1):
    a=str(Decimal(a)+Decimal(c[i]))
    a=str(Decimal('1')/Decimal(str(a)))

a=str(Decimal(a)+Decimal(c[0]))
b=str(Decimal(p[0])/Decimal(p[1]))


if(a==b):
    print("YES")
else:
    print("NO")


s = input().split(' ')

p = int(s[0])
q = int(s[1])

s = input()
n = int(s)

s = input().split(' ')

ok = True

for i in range(n):
    x = int(s[i])
    p = p-q*x
    if ok==False:
        continue
    if p==0 and i!=n-1 :
        ok = False
    elif p<0:
        ok = False
    t = p
    p = q
    q = t

if ok and (p==0 or q==0):
    print("YES")
else:
    print("NO")


p, q = [int(x) for x in input().split()]
n = int(input())
a = [int(x) for x in input().split()]
x, y = 1, 0
for i in a[::-1]:
    x, y = y+i*x, x
if x * q == y * p:
    print("YES")
else:
    print("NO")


p,q=[int(x) for x in input().split()]
n=int(input())
a=[int(x) for x in input().split()]

x,y,i=1,0,n
while n>0:
    x,y=y,x
    n-=1
    x+=y*a[n]

if x*q==y*p:
    print("YES")
else :
    print("NO")



def gcd(x,y):
    if(y == 0):
        return x
    else:
        return gcd(y,x%y) 

p, q = [int(i) for i in input().split()]
n = int(input())
a = [int(i) for i in input().split()]
x, y = 1, 0
for i in a[::-1]:
    x, y = y+i*x, x
a, b = gcd(p,q), gcd(x,y)
p = p // a;
q = q // a
x = x // b
y = y // b
if x == p and y == q:
    print("YES")
else:
    print("NO")


s = input()
a = s.split()
p = int(a[0])
q = int(a[1])
n = input()
s = input()
se = s.split()
for c in se:
    e = int(c)
    t1 = p-e*q
    t2 = q
    p = t2
    q = t1
if q == 0:
    print('YES')
else :
    print('NO')


def gcd(a,b):
    if(b==0):
        return a
    return gcd(b,a%b)
p,q=list(map(int,input().split()))
N=int(input())
A=list(map(int,input().split()))
znam=1
chisl=A[N-1]

for i in range (N-1,0,-1):
    chisl,znam=znam,chisl
    #print(chisl,znam)
    chisl += znam*A[i-1]
    #print(chisl,znam)
if(p*znam==q*chisl):
    print('YES')
else:
    print('NO')


def gcd (x, y):
    while (x > 0) and (y > 0):
        if (x > y):
            x %= y
        else:
            y %= x
    return x + y
p, q = map(int, input().split())
n = int (input ())
a = list (map (int, input ().split ()))
p1 = 1
q1 = a[n - 1]
for i in range(n - 2, -1, -1):
    p1 += a[i] * q1
    z = p1
    p1 = q1
    q1 = z
z = p1
p1 = q1
q1 = z
g = gcd (p, q)
if (g != 0):
    p /= g
    q /= g
g = gcd (p1, q1)
if (g != 0):
    p1 /= g
    q1 /= g
if (p == p1) and (q == q1):
    print ("YES")
else:
    print ("NO")

from fractions import Fraction
def __starting_point():
    p,q=list(map(int, input().split(' ')))
    n=int(input())
    a=list(map(int,input().split(' ')))
    def fract(x):
        if x==n-1:
            return Fraction(1,a[x])
        elif x>=n:
            return 0
        else:
            return Fraction(1,a[x]+fract(x+1))
    print('YES' if Fraction(p,q)==a[0]+fract(1) else 'NO')





__starting_point()

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

for i in range(n):
    p, q = q, p - A[i] * q

if p != 0 and q == 0:
    print('YES')
else:
    print('NO')