#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
bool isprime(long long value) {
  int cnt = 0;
  for (long long i = 1; i * i <= value; i++) {
    if (value % i == 0) {
      cnt++;
      if (i * i != value) {
        cnt++;
      }
    }
  }
  if (cnt == 2) {
    return true;
  } else {
    return false;
  }
}
long long fastpower(long long b, long long p) {
  long long ans = 1;
  while (p) {
    if (p % 2) {
      ans = (ans * b);
    }
    b = (b * b);
    p /= 2;
  }
  return ans;
}
string makeitstring(long long n) {
  string ans;
  if (n == 0) {
    ans = "0";
  };
  while (n) {
    long long mod = n % 10;
    mod += 48;
    char m = mod;
    ans = m + ans;
    n /= 10;
  }
  return ans;
}
long long makeitnumber(string s) {
  long long ans = 0;
  for (long long i = 0; i < s.size(); i++) {
    long long num = s[i] - '0';
    ans += (num * fastpower(10, (long long)s.size() - i - 1));
  }
  return ans;
}
bool valid(int x, int y, int n, int m) {
  return (x >= 0 && y < m && x < n && y >= 0);
}
string multiply(string one, string two) {
  string s;
  int cnt = 0;
  if (one[0] == '-') {
    reverse(one.begin(), one.end());
    one.pop_back();
    reverse(one.begin(), one.end());
    cnt++;
  }
  if (two[0] == '-') {
    reverse(two.begin(), two.end());
    two.pop_back();
    reverse(two.begin(), two.end());
    cnt++;
  }
  int n1 = one.size();
  int n2 = two.size();
  vector<int> ans(n1 + n2, 0);
  int pos1 = 0;
  int pos2 = 0;
  for (int i = n1 - 1; i >= 0; i--) {
    int carry = 0;
    int digit1 = one[i] - '0';
    pos2 = 0;
    for (int j = n2 - 1; j >= 0; j--) {
      int digit2 = two[j] - '0';
      int sum = (digit1 * digit2) + ans[pos1 + pos2] + carry;
      carry = sum / 10;
      ans[pos1 + pos2] = sum % 10;
      pos2++;
    }
    if (carry > 0) {
      ans[pos1 + pos2] += carry;
    }
    pos1++;
  }
  bool check = 0;
  for (int i = ans.size() - 1; i >= 0; i--) {
    if (ans[i]) {
      check = true;
    }
    if (check) {
      s += makeitstring(ans[i]);
    }
  }
  if (!check) {
    s += '0';
  }
  if (cnt % 2) {
    s = '-' + s;
  }
  return s;
}
string maxistring(string one, string two) {
  if (one[0] == '-' && two[0] != '-') {
    return two;
  } else if (one[0] != '-' && two[0] == '-') {
    return one;
  } else {
    if (one.size() > two.size() && one[0] != '-') {
      return one;
    } else if (one.size() < two.size() && one[0] != '-') {
      return two;
    } else if (one.size() > two.size() && one[0] == '-') {
      return two;
    } else if (one.size() < two.size() && one[0] == '-') {
      return one;
    } else {
      for (int i = 0; i < one.size(); i++) {
        if (one[0] != '-' && (one[i] - '0') > (two[i] - '0')) {
          return one;
        } else if (one[0] != '-' && (one[i] - '0') < (two[i] - '0')) {
          return two;
        } else if (one[0] == '-' && (one[i] - '0') > (two[i] - '0')) {
          return two;
        } else if (one[0] == '-' && (one[i] - '0') < (two[i] - '0')) {
          return one;
        }
      }
      return one;
    }
  }
}
double eps = 1e-9;
void comparing_doubles(double f, double s) {
  if (f - s > eps) {
    cout << "NO" << endl;
  } else if (f - s < -eps) {
    cout << "NO" << endl;
  } else {
    cout << "YES";
  }
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  if (a.first == b.first) {
    return (a.second < b.second);
  }
  return (a.first < b.first);
}
vector<unsigned long long> r1, r2;
void gen(unsigned long long a, unsigned long long b) {
  long long r = a / b;
  r2.push_back(r);
  a -= (b * r);
  if (!a) {
    return;
  }
  gen(b, a);
}
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  unsigned long long a, b;
  cin >> a >> b;
  unsigned long long n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    unsigned long long x;
    cin >> x;
    r1.push_back(x);
  }
  if (r1.size() > 1 && r1[r1.size() - 1] == 1) {
    r1.pop_back();
    r1[r1.size() - 1]++;
  }
  gen(a, b);
  if (r1 == r2) {
    cout << "YES";
  } else {
    cout << "NO";
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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>
using namespace std;
const int oo = 0x3f3f3f3f;
bool isprime(long long value) {
  int cnt = 0;
  for (long long i = 1; i * i <= value; i++) {
    if (value % i == 0) {
      cnt++;
      if (i * i != value) {
        cnt++;
      }
    }
  }
  if (cnt == 2) {
    return true;
  } else {
    return false;
  }
}
long long fastpower(long long b, long long p) {
  long long ans = 1;
  while (p) {
    if (p % 2) {
      ans = (ans * b);
    }
    b = (b * b);
    p /= 2;
  }
  return ans;
}
string makeitstring(long long n) {
  string ans;
  if (n == 0) {
    ans = "0";
  };
  while (n) {
    long long mod = n % 10;
    mod += 48;
    char m = mod;
    ans = m + ans;
    n /= 10;
  }
  return ans;
}
long long makeitnumber(string s) {
  long long ans = 0;
  for (long long i = 0; i < s.size(); i++) {
    long long num = s[i] - '0';
    ans += (num * fastpower(10, (long long)s.size() - i - 1));
  }
  return ans;
}
bool valid(int x, int y, int n, int m) {
  return (x >= 0 && y < m && x < n && y >= 0);
}
string multiply(string one, string two) {
  string s;
  int cnt = 0;
  if (one[0] == '-') {
    reverse(one.begin(), one.end());
    one.pop_back();
    reverse(one.begin(), one.end());
    cnt++;
  }
  if (two[0] == '-') {
    reverse(two.begin(), two.end());
    two.pop_back();
    reverse(two.begin(), two.end());
    cnt++;
  }
  int n1 = one.size();
  int n2 = two.size();
  vector<int> ans(n1 + n2, 0);
  int pos1 = 0;
  int pos2 = 0;
  for (int i = n1 - 1; i >= 0; i--) {
    int carry = 0;
    int digit1 = one[i] - '0';
    pos2 = 0;
    for (int j = n2 - 1; j >= 0; j--) {
      int digit2 = two[j] - '0';
      int sum = (digit1 * digit2) + ans[pos1 + pos2] + carry;
      carry = sum / 10;
      ans[pos1 + pos2] = sum % 10;
      pos2++;
    }
    if (carry > 0) {
      ans[pos1 + pos2] += carry;
    }
    pos1++;
  }
  bool check = 0;
  for (int i = ans.size() - 1; i >= 0; i--) {
    if (ans[i]) {
      check = true;
    }
    if (check) {
      s += makeitstring(ans[i]);
    }
  }
  if (!check) {
    s += '0';
  }
  if (cnt % 2) {
    s = '-' + s;
  }
  return s;
}
string maxistring(string one, string two) {
  if (one[0] == '-' && two[0] != '-') {
    return two;
  } else if (one[0] != '-' && two[0] == '-') {
    return one;
  } else {
    if (one.size() > two.size() && one[0] != '-') {
      return one;
    } else if (one.size() < two.size() && one[0] != '-') {
      return two;
    } else if (one.size() > two.size() && one[0] == '-') {
      return two;
    } else if (one.size() < two.size() && one[0] == '-') {
      return one;
    } else {
      for (int i = 0; i < one.size(); i++) {
        if (one[0] != '-' && (one[i] - '0') > (two[i] - '0')) {
          return one;
        } else if (one[0] != '-' && (one[i] - '0') < (two[i] - '0')) {
          return two;
        } else if (one[0] == '-' && (one[i] - '0') > (two[i] - '0')) {
          return two;
        } else if (one[0] == '-' && (one[i] - '0') < (two[i] - '0')) {
          return one;
        }
      }
      return one;
    }
  }
}
double eps = 1e-9;
void comparing_doubles(double f, double s) {
  if (f - s > eps) {
    cout << "NO" << endl;
  } else if (f - s < -eps) {
    cout << "NO" << endl;
  } else {
    cout << "YES";
  }
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  if (a.first == b.first) {
    return (a.second < b.second);
  }
  return (a.first < b.first);
}
vector<unsigned long long> r1, r2;
void gen(unsigned long long a, unsigned long long b) {
  long long r = a / b;
  r2.push_back(r);
  a -= (b * r);
  if (!a) {
    return;
  }
  gen(b, a);
}
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  unsigned long long a, b;
  cin >> a >> b;
  unsigned long long n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    unsigned long long x;
    cin >> x;
    r1.push_back(x);
  }
  if (r1.size() > 1 && r1[r1.size() - 1] == 1) {
    r1.pop_back();
    r1[r1.size() - 1]++;
  }
  gen(a, b);
  if (r1 == r2) {
    cout << "YES";
  } else {
    cout << "NO";
  }
  return 0;
}

```