cf487C Prefix Product Sequence

Consider a sequence [a₁, a₂, ... , a_n]. Define its prefix product sequence $\text{[math]}$ .

Now given n, find a permutation of [1, 2, ..., n], such that its prefix product sequence is a permutation of [0, 1, ..., n - 1].

Input

The only input line contains an integer n (1 ≤ n ≤ 10⁵).

Output

In the first output line, print "YES" if such sequence exists, or print "NO" if no such sequence exists.

If any solution exists, you should output n more lines. i-th line contains only an integer a_i. The elements of the sequence should be different positive integers no larger than n.

If there are multiple solutions, you are allowed to print any of them.

Example

Input

Output

Input

Output

NO

Note

For the second sample, there are no valid sequences.

要求给出1~n的排列，使得前1,2...n项之积模n恰好包含[0,n-1]中所有数

显然n要放最后，不然乘个n之后后面的积都是0了（不过这句话好像并没有卵用）

显然[0,n-1]每个数不能出现超过1次（好像也没有卵用）

如果n是质数，非常简单，令模n之后分别是1,2,3,4...n-1,0,

倒推可知第一个数是1，第二个数是2乘（1关于n的逆元），第三个数是3乘（2关于n的逆元）……最后一个是n

如果n不是质数，，，太恶心了

先给结论：如果n==4，发现有一解1,3,2,4是可以的，否则不行。

证明：当n为合数且n!=4，不妨假设n=p*q(p>2,p>=q)

那么1~pq当中有至少三个不同的数q,2q,pq。

显然n=pq是一定要放在排列最后的，再分类讨论：

p==q，n=p^2，而且p,2p的位置要在在p^2之前，显然p*2p=2p^2=2n,所以在p处，或者2p处前k项的积就是0了，p^2处也是0，显然不行

p!=q，p和q都在pq之前，同理，在p处，或者q处前k项的积是pq的倍数，所以也是0，而pq处也是0，也不行

*所以只有p==q==2的时候，没有p和2p同时出现，所以找到了一组解

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #include<deque>
 9 #include<set>
10 #include<map>
11 #include<ctime>
12 #define LL long long
13 #define inf 0x7ffffff
14 #define pa pair<int,int>
15 #define mkp(a,b) make_pair(a,b)
16 #define pi 3.1415926535897932384626433832795028841971
17 #define mod 100007
18 using namespace std;
19 inline LL read()
20 {
21     LL x=0,f=1;char ch=getchar();
22     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
23     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
24     return x*f;
25 }
26 int n;
27 LL ni[100010];
28 inline LL quickpow(LL a,int b)
29 {
30     LL s=1;
31     while (b)
32     {
33         if (b&1)s=(s*a)%n;
34         a=(a*a)%n;
35         b>>=1;
36     }
37     return s;
38 }
39 int main()
40 {
41     n=read();
42     if (n==1){puts("YES
1");return 0;}
43     if (n==4){puts("YES
1
3
2
4
");return 0;}
44     for (int i=2;i<=sqrt(n);i++)if (n%i==0){puts("NO");return 0;}
45     for (int i=1;i<n;i++)ni[i]=quickpow(i,n-2);
46     puts("YES");
47     puts("1");
48     for (int i=2;i<n;i++)printf("%d
",i*ni[i-1]%n);
49     printf("%d
",n);
50 }

cf487C

——by zhber，转载请注明来源