Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Circle of Numbers

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard output*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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/21/2019 05:35:21 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|