Consider a sequence [a_1, a_2, ... , a_{n}]. Define its prefix product sequence $[ a_{1} \operatorname{mod} n,(a_{1} a_{2}) \operatorname{mod} n, \cdots,(a_{1} a_{2} \cdots a_{n}) \operatorname{mod} n ]$.

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


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


-----Examples-----
Input
7

Output
YES
1
4
3
6
5
2
7

Input
6

Output
NO



-----Note-----

For the second sample, there are no valid sequences.

Difficulty: HARD
Tags: Number theory

Mathematics

Constructive algorithms

Starter code:

Solutions:
n = int(input())
if n == 1:
	print('YES\n1')
	exit(0)
if n == 4:
	print('YES\n1 3 2 4')
	exit(0)
for p in range(2, int(n ** 0.5) + 1):
	if n % p == 0:
		print('NO')
		exit(0)
print('YES')
print(1)
for j in range(2, n):
	print(j * pow(j - 1, n - 2, n) % n)
print(n)


import math
n = int(input())
if n == 1:
	print('YES', 1)
elif n == 4:
	print('YES', 1, 3, 2, 4, sep='\n')
else:
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			print('NO')
			exit()
	print('YES', 1, sep='\n')
	for i in range(2, n):
		print(i * pow(i - 1, n - 2, n) % n)
	print(n)


def comp(x):
	for i in range(2, x):
		if x % i == 0:
			return True
	return False
N = int(input())
if N == 4:
	print('YES', '1', '3', '2', '4', sep='\n')
elif comp(N):
	print('NO')
else:
	print('YES', '1', sep='\n')
	if N > 1:
		for i in range(2, N):
			print((i - 1) * pow(i, N - 2, N) % N)
		print(N)


n = int(input())
if n == 1:
	print('YES', 1)
	exit()
if n == 2:
	print('YES', 1, 2, sep='\n')
	exit()
if n == 4:
	print('YES', 1, 3, 2, 4, sep='\n')
	exit()
for i in range(2, n):
	if n % i == 0:
		print('NO')
		exit()
print('YES', 1, sep='\n')
for i in range(2, n):
	print(i * pow(i - 1, n - 2, n) % n)
print(n)


n = int(input())
if n == 4:
	print('YES\n1 3 2 4')
elif [i for i in range(2, n) if n % i == 0]:
	print('NO')
else:
	print('YES\n1 %s' % ' '.join((str(pow(x + 1, n - 2, n) * (x + 2) % n or n) for x in range(n - 1))))


import math
import sys
input = sys.stdin.readline
n = int(input())

def isPrime(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True
if isPrime(n):
	print('YES')
	print('\n'.join(list(map(str, [1] + [i * pow(i - 1, n - 2, n) % n for i in range(2, n)] + [n]))[:n]))
elif n == 4:
	print('YES')
	print('\n'.join(map(str, [1, 3, 2, 4])))
else:
	print('NO')


import math
import sys
input = sys.stdin.readline
n = int(input())
if math.factorial(n - 1) % n == n - 1:
	print('YES')
	print('\n'.join(list(map(str, [1] + [i * pow(i - 1, n - 2, n) % n for i in range(2, n)] + [n]))[:n]))
elif n == 4:
	print('YES')
	print('\n'.join(map(str, [1, 3, 2, 4])))
else:
	print('NO')


import sys
input = sys.stdin.readline

def check(a, n):
	x = 1
	s = set()
	for i in a:
		x = x * i % n
		if x in s:
			return False
		s.add(x)
	return True

def solve():
	n = int(input())
	if n == 4:
		print('YES\n1\n3\n2\n4\n')
		return
	if n == 1:
		print('YES\n1\n')
		return
	if n == 2:
		print('YES\n1\n2\n')
		return
	for i in range(2, n):
		if n % i == 0:
			print('NO')
			return
	m = n - 1
	d = []
	for i in range(2, m):
		if i * i > m:
			break
		if m % i == 0:
			d.append(i)
			m //= i
			while m % i == 0:
				m //= i
	if m != 1:
		d.append(m)
	m = n - 1
	for w in range(2, n):
		ok = True
		for i in d:
			if pow(w, n // i, n) == 1:
				ok = False
				break
		if ok:
			p = [None] * (n - 1)
			p[0] = 1
			p[1] = w
			x = w
			for i in range(2, n - 1):
				x = x * w % n
				p[i] = x
			print('YES')
			for i in range(0, m):
				print(p[i * (-1) ** i % m])
			print(n)
			return
	raise Exception('wut')
solve()


def is_prime(n):
	if n < 2:
		return False
	if n < 4:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i <= n ** 0.5:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i += 6
	return True
n = int(input())
if n == 4:
	print('YES\n1\n3\n2\n4')
elif n == 1:
	print('YES\n1')
elif not is_prime(n):
	print('NO')
else:
	print('YES\n1 %s' % ' '.join((str(pow(i + 1, n - 2, n) * (i + 2) % n or n) for i in range(n - 1))))