Circle of Numbers

题目描述

$ 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.

输入输出格式

输入格式

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.

输出格式

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).

输入输出样例

输入样例 #1

30
000100000100000110000000001100

输出样例 #1

YES

输入样例 #2

6
314159

输出样例 #2

NO

说明

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 $ .