_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).
[samples]
## 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.
**Definitions**
Let $ n \in \mathbb{Z} $, $ 3 \leq n \leq 100000 $, be the number of evenly spaced points on a circle.
Let $ s \in \{0,1,\dots,9\}^n $ be a string of $ n $ digits, representing initial values $ a_0, a_1, \dots, a_{n-1} \in \mathbb{Z} $ at points $ 0 $ to $ n-1 $ (clockwise).
Let $ k \in \mathbb{R}^+ $ be a chosen step size.
A *regular arithmetic progression modulo $ n $* is a subset of points $ \{ i, i+d, i+2d, \dots, i+(m-1)d \} \mod n $, for some $ d \in \{1,2,\dots,n-1\} $, $ m \geq 2 $, such that the points form a regular $ m $-gon (i.e., $ m \mid n $ and $ d = n/m $).
**Constraints**
1. $ n \geq 3 $
2. $ a_i \in \{0,1,\dots,9\} $ for all $ i \in \{0,1,\dots,n-1\} $
3. Operations: choose any regular arithmetic progression of size $ m \geq 2 $, and add or subtract $ k $ to all values at points in the progression.
**Objective**
Determine whether there exists a $ k > 0 $ and a finite sequence of such operations such that all $ a_i $ become $ 0 $.
**Equivalent Reformulation**
Let $ \mathcal{D} = \{ d \mid d = n/m, \, m \geq 2, \, m \mid n \} $.
For each $ d \in \mathcal{D} $, define the $ d $-cosets:
$ C_{d,j} = \{ j + td \mod n \mid t \in \mathbb{Z} \} $, for $ j = 0,1,\dots,d-1 $.
Each operation adds $ \pm k $ to all elements of one coset $ C_{d,j} $.
The problem reduces to:
Does there exist $ k > 0 $ and integers $ x_{d,j} \in \mathbb{Z} $ (net number of times we add $ +k $ minus $ -k $ on coset $ C_{d,j} $) such that:
$$
\sum_{\substack{d \in \mathcal{D} \\ j=0}}^{d-1} x_{d,j} \cdot \mathbf{1}_{i \in C_{d,j}} \cdot k = -a_i \quad \forall i \in \{0,1,\dots,n-1\}
$$
Equivalently, the vector $ \mathbf{a} = (a_0, \dots, a_{n-1}) $ must lie in the $ \mathbb{Z} $-span (over $ \mathbb{R} $) of the characteristic vectors of all regular cosets $ C_{d,j} $, scaled by $ k $.
**Key Insight**
Since operations are linear and additive, and $ k $ is a scalar multiplier, the necessary and sufficient condition is that the vector $ \mathbf{a} $ lies in the $ \mathbb{Q} $-vector space generated by the characteristic vectors of all regular $ m $-gon cosets (for $ m \mid n $, $ m \geq 2 $).
But since $ a_i \in \mathbb{Z} $, and operations use a common $ k $, we can scale:
Let $ \mathcal{V} \subseteq \mathbb{R}^n $ be the vector space spanned over $ \mathbb{Q} $ by all characteristic vectors of regular cosets.
Then:
> **Answer is YES** if and only if $ \mathbf{a} \in \mathcal{V} $.
However, a deeper number-theoretic structure applies:
Let $ \omega = e^{2\pi i / n} $.
The space $ \mathcal{V} $ is the direct sum of the eigenspaces of the cyclic shift operator corresponding to divisors $ d \mid n $, $ d < n $.
The necessary and sufficient condition is:
> The discrete Fourier transform $ \hat{a}_\ell = \sum_{j=0}^{n-1} a_j \omega^{j\ell} $ satisfies $ \hat{a}_\ell = 0 $ for all $ \ell $ such that $ \gcd(\ell, n) = 1 $.
**Final Formal Statement**
**Definitions**
Let $ n \in \mathbb{Z}_{\geq 3} $, $ \mathbf{a} = (a_0, a_1, \dots, a_{n-1}) \in \mathbb{Z}^n $.
Let $ \omega = e^{2\pi i / n} $.
For $ \ell = 0, 1, \dots, n-1 $, define the DFT:
$$
\hat{a}_\ell = \sum_{j=0}^{n-1} a_j \omega^{j\ell}
$$
**Objective**
Determine whether $ \hat{a}_\ell = 0 $ for all $ \ell \in \{1, 2, \dots, n-1\} $ such that $ \gcd(\ell, n) = 1 $.
If yes, output "YES"; otherwise, "NO".