#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1, 0};
long long fix_mod(long long x, long long y) { return (y + x % y) % y; }
void fast() {
  std::ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}
struct BigInteger {
  static const int BASE = 1000000000;
  vector<long long> digits;
  BigInteger() {
    digits.clear();
    digits.push_back(0);
  }
  BigInteger(long long number) {
    digits.clear();
    do {
      digits.push_back(number % BASE);
      number /= BASE;
    } while (number);
  }
  BigInteger operator+(const BigInteger &b) const {
    BigInteger res = BigInteger();
    res.digits.resize(max(b.digits.size(), digits.size()));
    long long remainder = 0;
    for (int i = 0, _n = (res.digits.size()); i < _n; i++) {
      if (i < digits.size()) remainder += digits[i];
      if (i < b.digits.size()) remainder += b.digits[i];
      res.digits[i] = remainder % BASE;
      remainder /= BASE;
    }
    while (remainder) {
      res.digits.push_back(remainder % BASE);
      remainder /= BASE;
    }
    return res;
  }
  BigInteger operator*(const BigInteger &b) const {
    BigInteger res = BigInteger();
    res.digits = vector<long long>(b.digits.size() + digits.size() - 1, 0);
    for (int i = 0, _n = (digits.size()); i < _n; i++)
      for (int j = 0, _n = (b.digits.size()); j < _n; j++)
        res.digits[i + j] += digits[i] * (long long)b.digits[j];
    long long remainder = 0;
    for (int i = 0, _n = (res.digits.size()); i < _n; i++) {
      remainder += res.digits[i];
      res.digits[i] = remainder % BASE;
      remainder /= BASE;
    }
    while (remainder) {
      res.digits.push_back(remainder % BASE);
      remainder /= BASE;
    }
    return res;
  }
  void print() {
    printf("%lld", digits.back());
    for (int i = ((int)digits.size() - 1) - 1; i >= 0; i--)
      printf("%09lld", digits[i]);
  }
  bool equal(long long x) {
    BigInteger b = BigInteger();
    b = b + x;
    if (b.digits.size() != digits.size()) return 0;
    for (int i = 0; i < digits.size(); i++) {
      if (b.digits[i] != digits[i]) return 0;
    }
    return 1;
  }
  static BigInteger power(const BigInteger &b, long long k) {
    if (k == 0) return BigInteger(1);
    if (k == 1) return b;
    BigInteger res = power(b, k / 2);
    res = res * res;
    if (k & 1) return res * b;
    return res;
  }
};
long long gcd(long long x, long long y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}
int main() {
  fast();
  long long p, q;
  cin >> p >> q;
  long long gc = gcd(p, q);
  p /= gc;
  q /= gc;
  int n;
  cin >> n;
  vector<long long> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  pair<BigInteger, BigInteger> res{v[n - 1], 1};
  for (int i = n - 2; i >= 0; i--) {
    swap(res.first, res.second);
    res.first = res.first + res.second * v[i];
  }
  cout << (res.first.equal(p) && res.second.equal(q) ? "YES" : "NO") << "\n";
}

### Prompt

Please provide a CPP coded solution to the problem described below:

A continued fraction of height n is a fraction of form <image>. 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 ≤ 1018) — 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 a1, a2, ..., an (1 ≤ ai ≤ 1018) — 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 <image>.

In the second sample <image>.

In the third sample <image>.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1, 0};
long long fix_mod(long long x, long long y) { return (y + x % y) % y; }
void fast() {
  std::ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}
struct BigInteger {
  static const int BASE = 1000000000;
  vector<long long> digits;
  BigInteger() {
    digits.clear();
    digits.push_back(0);
  }
  BigInteger(long long number) {
    digits.clear();
    do {
      digits.push_back(number % BASE);
      number /= BASE;
    } while (number);
  }
  BigInteger operator+(const BigInteger &b) const {
    BigInteger res = BigInteger();
    res.digits.resize(max(b.digits.size(), digits.size()));
    long long remainder = 0;
    for (int i = 0, _n = (res.digits.size()); i < _n; i++) {
      if (i < digits.size()) remainder += digits[i];
      if (i < b.digits.size()) remainder += b.digits[i];
      res.digits[i] = remainder % BASE;
      remainder /= BASE;
    }
    while (remainder) {
      res.digits.push_back(remainder % BASE);
      remainder /= BASE;
    }
    return res;
  }
  BigInteger operator*(const BigInteger &b) const {
    BigInteger res = BigInteger();
    res.digits = vector<long long>(b.digits.size() + digits.size() - 1, 0);
    for (int i = 0, _n = (digits.size()); i < _n; i++)
      for (int j = 0, _n = (b.digits.size()); j < _n; j++)
        res.digits[i + j] += digits[i] * (long long)b.digits[j];
    long long remainder = 0;
    for (int i = 0, _n = (res.digits.size()); i < _n; i++) {
      remainder += res.digits[i];
      res.digits[i] = remainder % BASE;
      remainder /= BASE;
    }
    while (remainder) {
      res.digits.push_back(remainder % BASE);
      remainder /= BASE;
    }
    return res;
  }
  void print() {
    printf("%lld", digits.back());
    for (int i = ((int)digits.size() - 1) - 1; i >= 0; i--)
      printf("%09lld", digits[i]);
  }
  bool equal(long long x) {
    BigInteger b = BigInteger();
    b = b + x;
    if (b.digits.size() != digits.size()) return 0;
    for (int i = 0; i < digits.size(); i++) {
      if (b.digits[i] != digits[i]) return 0;
    }
    return 1;
  }
  static BigInteger power(const BigInteger &b, long long k) {
    if (k == 0) return BigInteger(1);
    if (k == 1) return b;
    BigInteger res = power(b, k / 2);
    res = res * res;
    if (k & 1) return res * b;
    return res;
  }
};
long long gcd(long long x, long long y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}
int main() {
  fast();
  long long p, q;
  cin >> p >> q;
  long long gc = gcd(p, q);
  p /= gc;
  q /= gc;
  int n;
  cin >> n;
  vector<long long> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  pair<BigInteger, BigInteger> res{v[n - 1], 1};
  for (int i = n - 2; i >= 0; i--) {
    swap(res.first, res.second);
    res.first = res.first + res.second * v[i];
  }
  cout << (res.first.equal(p) && res.second.equal(q) ? "YES" : "NO") << "\n";
}

```