Problem: n evenly spaced points have been marked around the edge of a circle. There is a number written at each point. You choose a positive real number k. Then you may repeatedly select a set of 2 or more points which are evenly spaced, and either increase all numbers at points in the set by k or decrease all numbers at points in the set by k. You would like to eventually end up with all numbers equal to 0. Is it possible?

A set of 2 points is considered evenly spaced if they are diametrically opposed, and a set of 3 or more points is considered evenly spaced if they form a regular polygon.

Input

The first line of input contains an integer n (3 ≤ n ≤ 100000), the number of points along the circle.

The following line contains a string s with exactly n digits, indicating the numbers initially present at each of the points, in clockwise order.

Output

Print "YES" (without quotes) if there is some sequence of operations that results in all numbers being 0, otherwise "NO" (without quotes).

You can print each letter in any case (upper or lower).

Examples

Input

30
000100000100000110000000001100


Output

YES


Input

6
314159


Output

NO

Note

If we label the points from 1 to n, then for the first test case we can set k = 1. Then we increase the numbers at points 7 and 22 by 1, then decrease the numbers at points 7, 17, and 27 by 1, then decrease the numbers at points 4, 10, 16, 22, and 28 by 1.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int MOD2 = 1007681537;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
vector<int> dvs;
int fpow(int n, int k, int p) {
  int r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = (long long)r * n % p;
    n = (long long)n * n % p;
  }
  return r;
}
int primitiveroot(int p) {
  dvs.clear();
  for (int i = 2; i * i < p; i++) {
    if ((p - 1) % i) continue;
    dvs.push_back(i);
    if (i * i != p - 1) dvs.push_back((p - 1) / i);
  }
  for (int i = 2; i < p; i++) {
    int flag = 1;
    for (int j = 0; j < dvs.size(); j++) {
      if (fpow(i, dvs[j], p) == 1) {
        flag = 0;
        break;
      }
    }
    if (flag) return i;
  }
}
const int maxn = 4e5 + 5;
int n;
int a[maxn];
int ispr(int n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return 0;
    }
  }
  return 1;
}
void solve() {
  srand(time(NULL));
  cin >> n;
  string s;
  cin >> s;
  for (int i = (0); i < (n); i++) a[i] = s[i] - '0';
  while (1.0 * clock() / CLOCKS_PER_SEC < 0.8) {
    int st = INF + rand();
    while (st % n != 1 || !ispr(st)) st++;
    int p = st;
    int w = primitiveroot(p);
    w = fpow(w, (p - 1) / n, p);
    int r = 0;
    for (int i = (0); i < (n); i++) {
      r = mult(r, w, p);
      addmod(r, a[i], p);
    }
    if (r) {
      cout << "NO\n";
      return;
    }
  }
  cout << "YES\n";
}
int main() {
  int JUDGE_ONLINE = 1;
  if (fopen("in.txt", "r")) {
    JUDGE_ONLINE = 0;
    assert(freopen("in.txt", "r", stdin));
  } else {
    ios_base::sync_with_stdio(0), cin.tie(0);
  }
  solve();
  if (!JUDGE_ONLINE) {
  }
  return 0;
}