#include <bits/stdc++.h>
const int MAX_LEN = 1010;
using namespace std;
template <typename U, typename V>
string to_string(pair<U, V>);
string to_string(const string& e_) { return "\"" + e_ + "\""; }
string to_string(char e_) { return "\'" + string(1, e_) + "\'"; }
string to_string(bool e_) { return e_ ? "true" : "false"; }
template <typename T>
string to_string(T e_) {
  string s_ = "[ ";
  for (const auto& x_ : e_) s_ += to_string(x_) + " ";
  return s_ + "]";
}
template <typename U, typename V>
string to_string(pair<U, V> e_) {
  return "(" + to_string(e_.first) + ", " + to_string(e_.second) + ")";
}
void dbg_str() { ; }
template <typename U, typename... V>
void dbg_str(U u, V... v) {
  ;
  dbg_str(v...);
}
const long long int llmax = 1e18;
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
pair<long long int, long long int> getFraction(long long int a[],
                                               long long int size) {
  long long int n = 1;
  long long int d = a[size - 1];
  for (long long int i = size - 2; i >= 0; i--) {
    if (a[i] > llmax / d) return pair<long long int, long long int>(-1, -1);
    long long int nextd = d * a[i] + n;
    n = d;
    d = nextd;
  }
  return pair<long long int, long long int>(d, n);
}
long long int p, q;
int n;
long long int a[100];
int main() {
  scanf("%lld %lld", &p, &q);
  long long int g = gcd(p, q);
  p /= g;
  q /= g;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
  pair<long long int, long long int> ans = getFraction(a, n);
  ;
  if (ans.first == p && ans.second == q)
    printf("YES\n");
  else
    printf("NO\n");
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

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>
const int MAX_LEN = 1010;
using namespace std;
template <typename U, typename V>
string to_string(pair<U, V>);
string to_string(const string& e_) { return "\"" + e_ + "\""; }
string to_string(char e_) { return "\'" + string(1, e_) + "\'"; }
string to_string(bool e_) { return e_ ? "true" : "false"; }
template <typename T>
string to_string(T e_) {
  string s_ = "[ ";
  for (const auto& x_ : e_) s_ += to_string(x_) + " ";
  return s_ + "]";
}
template <typename U, typename V>
string to_string(pair<U, V> e_) {
  return "(" + to_string(e_.first) + ", " + to_string(e_.second) + ")";
}
void dbg_str() { ; }
template <typename U, typename... V>
void dbg_str(U u, V... v) {
  ;
  dbg_str(v...);
}
const long long int llmax = 1e18;
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
pair<long long int, long long int> getFraction(long long int a[],
                                               long long int size) {
  long long int n = 1;
  long long int d = a[size - 1];
  for (long long int i = size - 2; i >= 0; i--) {
    if (a[i] > llmax / d) return pair<long long int, long long int>(-1, -1);
    long long int nextd = d * a[i] + n;
    n = d;
    d = nextd;
  }
  return pair<long long int, long long int>(d, n);
}
long long int p, q;
int n;
long long int a[100];
int main() {
  scanf("%lld %lld", &p, &q);
  long long int g = gcd(p, q);
  p /= g;
  q /= g;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
  pair<long long int, long long int> ans = getFraction(a, n);
  ;
  if (ans.first == p && ans.second == q)
    printf("YES\n");
  else
    printf("NO\n");
}

```