Now you get Baby Ehab's first words: "Given an integer $n$, find the longest subsequence of $[1,2, \ldots, n-1]$ whose product is $1$ modulo $n$." Please solve the problem.

A sequence $b$ is a subsequence of an array $a$ if $b$ can be obtained from $a$ by deleting some (possibly all) elements. The product of an empty subsequence is equal to $1$.


-----Input-----

The only line contains the integer $n$ ($2 \le n \le 10^5$).


-----Output-----

The first line should contain a single integer, the length of the longest subsequence.

The second line should contain the elements of the subsequence, in increasing order.

If there are multiple solutions, you can print any.


-----Examples-----

Input
5
Output
3
1 2 3
Input
8
Output
4
1 3 5 7


-----Note-----

In the first example, the product of the elements is $6$ which is congruent to $1$ modulo $5$. The only longer subsequence is $[1,2,3,4]$. Its product is $24$ which is congruent to $4$ modulo $5$. Hence, the answer is $[1,2,3]$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Number theory

Greedy algorithms


Solutions:
from math import gcd
n = int(input())
li = []
factorial = 1
for i in range(1, n):
	if gcd(n, i) == 1:
		li.append(i)
		factorial = factorial * i % n
if factorial == 1:
	print(len(li))
	print(*li)
else:
	print(len(li) - 1)
	print(*li[:len(li) - 1])


from math import gcd

def coprime(a, b):
	return gcd(a, b) == 1
N = int(input())
ans = [1]
count = 1
mod = 1
for x in range(2, N):
	if coprime(x, N):
		ans += (x,)
		count += 1
		mod = mod * x % N
if mod != 1:
	del ans[-1]
	count -= 1
print(count)
print(' '.join(map(str, ans)))


from math import gcd
n = int(input())
ans = []
cal = 1
for i in range(1, n - 1):
	if gcd(i, n) == 1:
		ans.append(i)
		cal = cal * i % n
cal = cal * (n - 1) % n
if cal == 1:
	ans.append(n - 1)
print(len(ans))
print(*ans)


import math
n = int(input())
ans = []
x = 1
for i in range(1, n):
	if math.gcd(n, i) == 1:
		ans.append(i)
		x = x * i % n
if x != 1:
	ans.remove(x)
print(len(ans))
print(*ans)


from math import gcd, prod
n = int(input())
comprime_n = [i for i in range(1, n) if gcd(i, n) == 1]
mod = 1
for cp in comprime_n:
	mod = mod * cp % n
if mod % n != 1:
	comprime_n.pop()
print(len(comprime_n))
print(*comprime_n)


import math

def question3():
	N = int(input())
	ans = [1]
	pro = 1
	for i in range(2, N):
		if math.gcd(N, i) == 1:
			ans.append(i)
			pro = pro * i % N
	if pro > 1:
		ans.pop()
	if len(ans) == 0:
		return (1, [1])
	return (len(ans), ans)
remained_test_cases = 1
while remained_test_cases > 0:
	(len1, ans) = question3()
	print(len1)
	print(*ans)
	remained_test_cases -= 1


import math
from sys import stdin
input = stdin.readline
n = int(input())
t = [1]
p = 1
for i in range(2, n - 1):
	if math.gcd(i, n) == 1:
		t.append(i)
		p *= i
		p %= n
if p % n != 1:
	t.append(n - 1)
	p *= n - 1
print(len(t))
print(*t)


import math
a = [0 for i in range(100007)]
ans = 1
n = int(input())
for i in range(1, n):
	if math.gcd(n, i) == 1:
		a[i] = 1
		ans = int(ans * i % n)
if int(ans) != 1:
	a[int(ans)] = 0
print(a.count(1))
for i in range(1, n):
	if a[i]:
		print(i, end=' ')


import math

def mod1p():
	n = int(input())
	ans = dict()
	p = 1
	for i in range(1, n):
		if math.gcd(i, n) == 1:
			ans[i] = True
			p = p * i % n
	if p == 1:
		print(len(ans))
		print(*ans.keys())
	else:
		ans.pop(p)
		print(len(ans))
		print(*ans.keys())
mod1p()


from math import gcd
n = int(input())
ans = 1
l = [1]
for i in range(2, n):
	if gcd(n, i) == 1:
		l.append(i)
		ans = ans * i % n
if ans == 1:
	print(len(l))
	print(*l)
else:
	print(len(l) - 1)
	print(*l[:-1])


import sys, os, io
from math import gcd
n = int(input())
a = []
mod = 10 ** 9 + 7
for i in range(1, n):
	if gcd(i, n) == 1:
		a.append(i)
curr = 1
for i in a:
	curr *= i
	curr %= n
if curr == 1:
	print(len(a))
	print(*a)
else:
	print(len(a) - 1)
	print(*a[:-1])


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
n = I()
p = 1
v = []
for i in range(1, n):
	if gcd(n, i) == 1:
		p = p * i % n
		v += (i,)
if p != 1:
	v.remove(p)
print(len(v))
print(*v)


from sys import stdin, stdout
get_string = lambda : stdin.readline().strip(' ')
get_intmap = lambda : map(int, get_string().split(' '))

def testcase():
	n = n1 = int(input())
	prime_factors = []
	for i in range(2, int(n ** 0.5) + 4):
		(q, r) = divmod(n1, i)
		if r == 0:
			prime_factors.append(i)
			while r == 0:
				n1 = q
				(q, r) = divmod(n1, i)
	if n1 > 1:
		prime_factors.append(n1)
	(coprimes, prod) = ([], 1)
	for i in range(1, n):
		ok = True
		for prime in prime_factors:
			ok = i % prime
			if prime > i or not ok:
				break
		if ok:
			coprimes.append(i)
			prod = prod * i % n
	if prod != 1:
		coprimes.remove(prod)
	print(len(coprimes))
	print(' '.join([str(i) for i in coprimes]))
testcase()
quit()
for t in range(int(input())):
	testcase()


from math import gcd
n = int(input())
a = [i for i in range(1, n) if gcd(i, n) == 1]
p = 1
for i in a:
	p = p * i % n
if p == 1:
	print(len(a))
	print(*a)
else:
	print(len(a) - 1)
	print(*[i for i in a if i != p])


from math import gcd
n = int(input())
pr = 1
ans = []
for i in range(1, n):
	if gcd(n, i) == 1:
		ans.append(i)
		pr = pr * i % n
if pr == 1:
	print(len(ans))
	print(*ans)
else:
	del ans[ans.index(pr)]
	print(len(ans))
	print(*ans)


from sys import stdin
f = stdin
n = int(f.read())
from functools import reduce

def is_rel_p(a, b):
	(a, b) = (min(a, b), max(a, b))
	while b % a != 0:
		if a == 0:
			break
		b = b % a
		(a, b) = (min(a, b), max(a, b))
	return min(a, b) == 1
nums_good = [True for i in range(0, n)]
nums_good[1] = True
for i in range(2, n):
	if n % i == 0:
		for j in range(i, n, i):
			nums_good[j] = False
numset = set(filter(lambda x: nums_good[x], list(range(1, n))))
muled = reduce(lambda a, b: a * b % n, numset)
while muled % n != 1:
	value = muled % n
	numset.remove(value)
	muled //= value
print(len(numset))
print(' '.join(map(str, sorted(numset))))


import math
n = int(input())
ans = 1
answer = [1]
i = 2
prod = 1
while i < n:
	if math.gcd(n, i) == 1:
		answer.append(i)
		ans += 1
		prod *= i
		prod %= n
	i += 1
if prod != 1:
	del answer[-1]
	ans -= 1
print(ans)
print(' '.join(map(str, answer)))


import sys
import math
mod = 10 ** 9 + 7
LI = lambda : [int(k) for k in input().split()]
input = lambda : sys.stdin.readline().rstrip()
IN = lambda : int(input())
S = lambda : input()
n = IN()
li = []
pro = 1
for i in range(1, n):
	if math.gcd(n, i) == 1:
		li.append(i)
		pro *= i
		pro %= n
if pro != 1:
	li.remove(pro)
print(len(li))
print(*li)


import math
n = int(input())
a = []
for j in range(1, n):
	if math.gcd(n, j) == 1:
		a.append(j)
b = 1
for j in range(len(a)):
	b = b * a[j] % n
if b == 1:
	print(len(a))
	print(' '.join(map(str, a)))
else:
	c = []
	for j in range(len(a)):
		if a[j] != b:
			c.append(a[j])
	print(len(a) - 1)
	print(' '.join(map(str, c)))


from math import gcd
N = int(input())
ok = [0] * 100005
prod = 1
for i in range(1, N):
	if gcd(i, N) == 1:
		ok[i] = 1
		prod = prod * i % N
if prod != 1:
	ok[prod] = 0
valid = [i for i in range(N) if ok[i] == 1]
print(len(valid))
print(*valid)


from math import gcd
n = int(input())
a = []
pro = 1
for i in range(1, n):
	if gcd(n, i) == 1:
		a.append(i)
		pro = pro * i % n
if pro != 1:
	a.remove(pro)
print(len(a))
print(*a)


import math
import sys

def inp():
	return sys.stdin.readline().strip()
n = int(inp())
ans = []
product = 1
for i in range(1, n):
	if math.gcd(n, i) == 1:
		ans.append(i)
		product = product * i % n
if product != 1:
	ans.pop()
print(len(ans))
print(*ans)


import sys
import math
input = sys.stdin.readline

def main():
	n = int(input())
	seq = list(range(1, n))
	a = []
	prod = 1
	for i in range(n - 1):
		if math.gcd(seq[i], n) == 1:
			a.append(seq[i])
			prod *= seq[i]
			prod %= n
	ans = []
	for j in a:
		if prod > 1 and j == prod:
			pass
		else:
			ans.append(j)
	print(len(ans))
	print(*ans)
main()


from math import gcd

def mlt():
	return map(int, input().split())
x = int(input())
vis = {}
pd = 1
res = 0
for n in range(x):
	if gcd(x, n) == 1:
		pd *= n
		pd %= x
		res += 1
		vis[n] = 1
	else:
		vis[n] = 0
if pd != 1:
	vis[pd] = 0
	res -= 1
print(res)
for n in range(x):
	if vis[n]:
		print(n, end=' ')


from math import gcd
n = int(input())
a = [0] * (n + 1)
p = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		a[i] = 1
		p = p * i % n
if p != 1:
	a[p] = 0
print(a.count(1))
for i in range(1, n + 1):
	if a[i]:
		print(i, end=' ')


from math import gcd
n = int(input())

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
pos = set()
neg = set()
for i in range(2, n - 1):
	if gcd(n, i) == 1:
		inv = modInverse(i, n)
		if i == inv:
			neg.add(i)
			neg.add(n - i)
		else:
			pos.add(i)
			pos.add(inv)
l = len(neg)
if l % 4 == 2:
	neg.add(1)
	neg.add(n - 1)
else:
	pos.add(1)
neg = list(neg)
pos = list(pos)
ans = pos + neg
ans.sort()
print(len(ans))
print(*ans)


from math import gcd
n = [int(i) for i in input().split()][0]
mods = [0] * n
res = []
prod = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		res += [str(i)]
		prod *= i
		prod %= n
if prod != 1:
	res = res[:-1]
print(len(res))
print(' '.join(res))


N = int(input())
divs = set()
m = 2
while m * m <= N:
	if N % m == 0:
		divs.add(m)
		divs.add(N // m)
	m += 1
ans = set(range(1, N))
for d in divs:
	for n in range(d, N, d):
		if n in ans:
			ans.remove(n)
ans = sorted(ans)
r = 1
for a in ans:
	r *= a
	r %= N
if r == 1:
	print(len(ans))
	print(*ans)
	exit()
ans.pop()
r = 1
for a in ans:
	r *= a
	r %= N
if r == 1:
	print(len(ans))
	print(*ans)
else:
	print(len(ans))
	print(*ans)
	assert False


import math
n = int(input())
ans = []
out = 1
for i in range(1, n):
	if math.gcd(i, n) == 1:
		out = i * out % n
		ans.append(i)
if out % n == 1:
	print(len(ans))
	print(*ans)
else:
	ans.pop()
	print(len(ans))
	print(*ans)


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
n = I()
ans = []
for i in range(1, n):
	if math.gcd(n, i) == 1:
		ans.append(i)
tmp = 1
for i in ans:
	tmp *= i
	tmp %= n
if tmp == 1:
	print(len(ans))
	print(*ans)
else:
	print(len(ans) - 1)
	print(*ans[:-1])


import math
n = int(input())
ans = []
prod = 1
count = 0
for i in range(1, n - 1):
	if math.gcd(n, i) == 1:
		ans.append(str(i))
		prod = prod * i % n
		count += 1
if n == 2:
	print(1)
	print(1)
elif prod % n == 1:
	print(count)
	print(' '.join(ans))
else:
	print(count + 1)
	print(' '.join(ans), n - 1)


import math
(n, p) = (int(input()), 1)
store_value = set()
for i in range(1, n):
	if math.gcd(i, n) == 1:
		store_value.add(i)
		p = p * i % n
if p != 1:
	store_value.remove(p)
print(len(store_value))
print(*sorted(list(store_value)))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
max_n = 200000
mod = 10 ** 9 + 7
if 1:
	max_n = min(max_n, mod - 1)
	(fact, inv_fact) = ([0] * (max_n + 1), [0] * (max_n + 1))
	fact[0] = 1
	for i in range(max_n):
		fact[i + 1] = fact[i] * (i + 1) % mod
	inv_fact[-1] = pow(fact[-1], mod - 2, mod)
	for i in reversed(range(max_n)):
		inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

	def nCr_mod(n, r):
		res = 1
		while n or r:
			(a, b) = (n % mod, r % mod)
			if a < b:
				return 0
			res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
			n //= mod
			r //= mod
		return res

def SieveOfEratosthenes(limit=10 ** 6):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes
sv = SieveOfEratosthenes(10 ** 5 + 6969)
for _ in range(int(input()) if not True else 1):
	n = int(input())
	if n <= 4:
		print(1)
		print(1)
		continue
	if n in sv:
		a = [i + 1 for i in range(n - 2)]
	else:
		a = [1]
		for i in range(2, n):
			if gcd(n, i) == 1:
				a += [i]
	if prod(a, n) == 1:
		print(len(a))
		print(*a)
	else:
		a.pop()
		print(len(a))
		print(*a)
	assert prod(a, n) == 1


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
res = []
n = int(input())
if n == 2:
	print(1)
	print(1)
else:
	prod = 1
	res = [x for x in range(n) if gcd(x, n) == 1]
	for i in res:
		prod = prod * i % n
	if prod != 1:
		res.pop()
	print(len(res))
	print(*res)


from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
from math import *

def main():
	n = int(input())
	mul = 1
	good = [1]
	for i in range(2, n):
		if gcd(n, i) == 1:
			mul *= i
			mul %= n
			good.append(i)
	if mul == 1:
		print(str(len(good)) + '\n')
	else:
		print(str(len(good) - 1) + '\n')
	for elem in good:
		if elem != mul or mul == 1:
			print(str(elem) + ' ')
main()


import sys, math
from math import gcd
from operator import xor
md = 1000000007
n = int(input())
d = []
p = 1
for i in range(1, n):
	if gcd(n, i) == 1:
		d.append(i)
		p = p * i % n
if p != 1:
	d.pop()
print(len(d))
print(*d)


n = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
length = 0
product = 1
P = []
for i in range(1, n):
	if gcd(i, n) == 1:
		product = product * i % n
		P.append(i)
		length += 1
if product == n - 1 and n != 2:
	P.pop()
	length -= 1
print(length)
print(*P)


import sys
from math import factorial, ceil

def gcd(a, b):
	return b if a == 0 else gcd(b % a, a)

def solve():
	n = int(input())
	l = [i for i in range(1, n) if gcd(i, n) == 1]
	x = 1
	for i in l:
		x = x * i % n
	if x != 1:
		l.remove(x)
	print(len(l))
	print(*l)
solve()


from collections import Counter
from sys import stdin, stdout
import math

def coprime(a, b):
	if math.gcd(a, b) == 1:
		return True
	else:
		return False

def product(a, n):
	ans = 1
	for i in a:
		ans = ans * i
		ans = ans % n
	return ans
n = int(stdin.readline())
l = []
for i in range(1, n):
	if coprime(i, n) == True:
		l.append(i)
a = product(l, n)
while a != 1:
	if a in l:
		l.remove(a)
	a = product(l, n)
print(len(l))
print(*l)


import os
import sys
from io import BytesIO, IOBase
from math import gcd

def main():
	n = int(input())
	a = []
	p = 1
	for i in range(1, n):
		if gcd(i, n) == 1:
			a.append(i)
			p = p * i % n
	if p != 1:
		a.remove(p)
	print(len(a))
	print(*a)

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()


import math
n = int(input())
a = 0
s = []
p = 1
for i in range(n):
	if math.gcd(i, n) == 1:
		a += 1
		s += [i]
		p *= i
		p %= n
if p != 1:
	a -= 1
	s.remove(p)
print(a)
print(*s)


def prod(arr):
	p = 1
	for i in arr:
		p = p * i % n
	return p
n = int(input())
lst = [0] * n
for i in range(2, n // 2 + 1):
	if not n % i:
		j = i
		while j < n:
			lst[j] = 1
			j += i
arr = [i for i in range(1, n) if lst[i] == 0]
x = prod(arr)
if x != 1:
	arr.pop()
print(len(arr))
print(*arr)


import math
n = int(input())
ar1 = []
prd = 1
for j in range(1, n):
	if math.gcd(j, n) == 1:
		ar1.append(j)
		prd = prd * j % n
if prd != 1:
	ar1.pop(-1)
print(len(ar1))
print(*ar1)


from math import gcd
N = int(input())
Dta = []
for i in range(1, N):
	if gcd(i, N) == 1:
		Dta.append(i)
Prod = 1
for x in Dta:
	Prod = Prod * x % N
if Prod != 1:
	Dta.remove(Prod)
print(len(Dta))
print(*Dta)


from math import gcd
n = int(input())
lst = []
product = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		lst.append(i)
		product = product * i % n
if product % n != 1:
	lst.pop()
print(len(lst))
print(*lst)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
n = I()
a = [0] * n
p = 1
c = 0
for i in range(1, n):
	if math.gcd(i, n) == 1:
		a[i] = 1
		c += 1
		p = p * i % n
if p != 1:
	a[p] = 0
	c -= 1
print(c)
for i in range(1, n):
	if a[i] == 1:
		print(i, end=' ')
print()


def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
n = int(input())
prod = 1
H = [0] * 100005
for i in range(1, n + 1):
	if computeGCD(n, i) == 1:
		H[i] = 1
		prod = prod * i % n
if prod != 1:
	H[prod] = 0
print(H.count(1))
for i in range(1, n):
	if H[i]:
		print(i, end=' ')


from math import gcd
n = int(input())
lst = [0] * n
mul = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		lst[i] = 1
		mul = mul * i % n
if mul != 1:
	lst[mul] = 0
print(lst.count(1))
for i in range(len(lst)):
	if lst[i]:
		print(i, end=' ')


from math import gcd

def f(n):
	ok = [0] * (2 * 10 ** 5)
	p = 1
	for i in range(1, n):
		if gcd(n, i) == 1:
			ok[i] = 1
			p = p * i % n
	if p != 1:
		ok[p] = 0
	print(ok.count(1))
	for i in range(len(ok)):
		if ok[i] == 1:
			print(i, end=' ')
	return ''
print(*f(int(input())))


import math
n = int(input())
list1 = list()
pro = 1
for i in range(1, n):
	if math.gcd(i, n) == 1:
		list1.append(i)
		pro = pro % n * i % n % n
		pro = pro % n
if pro == 1:
	print(len(list1))
	print(*list1)
else:
	print(len(list1) - 1)
	for i in range(len(list1)):
		if list1[i] == pro:
			pass
		else:
			print(list1[i], end=' ')
	print()


import math

def isprime(n):
	if n < 2:
		return False
	i = 2
	while i <= math.sqrt(n):
		if n % i == 0:
			return False
		i += 1
	return True

def get_answer(n):
	total = 0
	modsum = 1
	b = []
	for v in range(1, n):
		if math.gcd(v, n) == 1:
			total += 1
			modsum = modsum * v % n
			b.append(v)
	if modsum == 1:
		print(total)
		print(*b)
	else:
		print(total - 1)
		print(*b[:-1])
n = int(input())
get_answer(n)


import math
n = int(input())
modulo = []
p = 1
for i in range(1, n):
	if math.gcd(i, n) == 1:
		p = p * i % n
		modulo.append(i)
if p % n == 1:
	print(len(modulo))
	for i in modulo:
		print(i, end=' ')
else:
	z = p % n
	print(len(modulo) - 1)
	for i in modulo:
		if i != z:
			print(i, end=' ')


from math import gcd
n = int(input())
p = []
for i in range(2, n):
	if gcd(n, i) == 1:
		p.append(i)
ans = [1]
l = []
x = 1
for pp in p:
	x *= pp
	x %= n
	l.append(pp)
	if x == 1:
		ans += l
		l = []
print(len(ans))
print(*ans)


import math
n = int(input())
res = []
p = 1
for i in range(1, n):
	if math.gcd(n, i) == 1:
		p = p * i % n
		res.append(i)
if p != 1:
	res.remove(p)
print(len(res))
print(*res)


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s.rstrip())

def invr():
	return map(int, input().split())
n = inp()
if n == 2:
	print(1)
	print(1)
else:
	L = []
	V = 1
	for d in range(1, n):
		if math.gcd(d, n) == 1:
			L.append(d)
			V = V * d % n
	if len(L) == n - 1:
		print(n - 2)
		print(' '.join(list(map(str, [i for i in range(1, n - 1)]))))
	else:
		if V != 1:
			L.pop()
		print(len(L))
		print(' '.join(list(map(str, L))))


from itertools import combinations
from math import gcd
n = int(input())
ok = [True for _ in range(n)]

def primes(n):
	res = set()
	i = 2
	while n > 1:
		if n % i == 0:
			res.add(i)
			n = n // i
		else:
			i += 1
	return res
n_primes = primes(n)
for p in n_primes:
	for i in range(p, n, p):
		ok[i] = False
if n == 2:
	print(1)
	print(1)
elif n in n_primes:
	print(n - 2)
	print(*range(1, n - 1))
else:
	res = [i for (i, v) in enumerate(ok) if v and i > 0]
	product = [i for i in res]
	for (i, v) in enumerate(res):
		if i == 0:
			continue
		product[i] = product[i - 1] * v % n
	r = len(res) - 1
	while product[r] != 1:
		r -= 1
	print(r + 1)
	print(*(v for (i, v) in enumerate(res) if i <= r))


from itertools import product
import itertools
import sys
import heapq
import math
from collections import deque
MOD = 10 ** 9 + 7

def find(parent, i):
	if parent[i] != i:
		parent[i] = find(parent, parent[i])
	return parent[i]

def union(parent, rank, xx, yy):
	x = find(parent, xx)
	y = find(parent, yy)
	if rank[x] > rank[y]:
		parent[y] = x
	elif rank[y] > rank[x]:
		parent[x] = y
	else:
		parent[y] = x
		rank[x] += 1

def factorof(div, n):
	if n % div == 0:
		return True
	else:
		return False

def minfactor(n):
	for i in range(2, n + 1):
		if factorof(i, n):
			return i

def factoring(n):
	fct = []
	while n > 1:
		f = minfactor(n)
		n = n // f
		match = False
		for i in range(0, len(fct)):
			if fct[i][0] == f:
				fct[i][1] = fct[i][1] + 1
				match = True
				break
			if fct[i][0] > f:
				break
		if not match:
			fct.append([f, 1])
	return fct
ans = 0
K = int(sys.stdin.readline().strip())
from math import gcd as bltin_gcd

def coprime2(a, b):
	return bltin_gcd(a, b) == 1
x = 0
y = 0
ans = 1
l = []
for n in range(1, K):
	if coprime2(n, K):
		l.append(n)
		ans *= n
		ans = ans % K
if ans % K != 1:
	l.pop()
print(len(l))
for i in range(len(l)):
	l[i] = str(l[i])
print(' '.join(l))


def gcd(a, b):
	while b != 0:
		a = a % b
		(a, b) = (b, a)
	return a
n = int(input())
res = [1]
prod = 1
for i in range(2, n):
	if gcd(n, i) == 1:
		res.append(i)
		prod = prod * i % n
if prod != 1:
	res.remove(prod)
print(len(res))
print(' '.join((str(r) for r in res)))


import math
n = int(input())
ans = 1
p = 0
l = []
for i in range(1, n):
	if math.gcd(i, n) == 1:
		ans *= i
		l.append(i)
		ans = ans % n
if ans % n != 1:
	l.pop()
print(len(l))
print(*l)


def f(n):
	l = []
	i = 2
	while i <= n ** 0.5:
		if n % i != 0:
			i += 1
		else:
			l.append(i)
			n //= i
	if n != 1:
		l.append(n)
	if len(l) == 1:
		x = 2
	elif l == [2, 2]:
		x = 2
	elif len(l) == 2:
		if l[0] == 2:
			x = 2
		elif l[0] == l[1]:
			x = 2
		else:
			x = 4
	elif l[2] == 2:
		x = 4
	elif l[0] == l[-1]:
		x = 2
	elif l[0] == 2 and l[1] == l[-1]:
		x = 2
	else:
		x = 4
	return [x, l]
n = int(input())
l = []
m = f(n)
x = set(m[1])
for i in range(1, n):
	y = 0
	for j in x:
		if i % j == 0:
			y = 1
	if y == 0:
		l.append(i)
a = ''
if n == 2:
	print(1)
	print(1)
elif m[0] == 2:
	for i in l[:-1]:
		a += str(i) + ' '
	print(len(l) - 1)
	print(a[:-1])
else:
	for i in l:
		a += str(i) + ' '
	print(len(l))
	print(a[:-1])


import math
n = int(input())
s = 1 if n % 2 == 1 else 2
arr = []
prod = 1
for i in range(1, n, s):
	if math.gcd(n, i) == 1:
		arr.append(i)
for j in range(len(arr)):
	prod = prod * arr[j] % n
if prod != 1:
	arr.remove(prod)
print(len(arr))
print(*arr)


from typing import List
from math import gcd

def optimal(size: int) -> List[int]:
	(invalid, valid) = (1, list())
	for value in range(1, size):
		if not gcd(size, value) - 1:
			valid.append(value)
			invalid = invalid * value % size
	invalid = None if not invalid - 1 else invalid
	return [item for item in valid if item != invalid]

def read_input(filename: str=None) -> None:
	from sys import stdin
	stdin = open(filename) if filename else stdin
	size = int(stdin.readline())
	valid = optimal(size)
	print(len(valid))
	print(*valid)

def main():
	read_input()
main()


from sys import stdin, stdout, version_info
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
ml = [i for i in range(1, n)]
take = l1d(n, False)
modarr = [1]
take[1] = True
divs = []
for i in range(2, int(sqrt(n)) + 1):
	if n % i == 0:
		divs.append(i)
		if n != i * i:
			divs.append(n // i)
for i in range(2, n):
	x = modarr[-1]
	if gcd(n, i) == 1:
		take[i] = True
		x = x * i % n
	modarr.append(x)
for i in range(n - 2, -1, -1):
	if modarr[i] == 1:
		break
ansl = []
for j in range(i + 1):
	if take[j + 1]:
		ansl.append(j + 1)
print(len(ansl))
print(*ansl)


import sys
import math
from math import factorial, inf, gcd
from heapq import *
from functools import *
from itertools import *
from collections import *
from typing import *
from bisect import *
sys.setrecursionlimit(10 ** 5)

def rarray():
	return [int(i) for i in input().split()]
ti = 1
for ii in range(ti):
	n = int(input())
	ans = [i for i in range(1, n) if gcd(i, n) == 1]
	a = 1
	res = 0
	for i in range(1, len(ans)):
		a = a * ans[i] % n
		if a == 1:
			res = i
	print(res + 1)
	for i in ans[:res + 1]:
		print(i, end=' ')
	print()


from math import gcd
a = []
b = 1
n = int(input())
for i in range(n):
	if gcd(i, n) == 1:
		a.append(i)
		b = b * i % n
for i in range(len(a) - 1, -1, -1):
	if b % n != 1:
		b //= a[i]
		a.pop()
print(len(a))
print(*a)


import math
from sys import stdin, stdout
input = stdin.readline
lis = []
n = int(input())
prod = 1
for i in range(1, n - 1):
	if math.gcd(n, i) == 1:
		prod = prod * i % n
		lis.append(i)
if prod * (n - 1) % n == 1 and math.gcd(n, n - 1) == 1:
	lis.append(n - 1)
print(len(lis))
print(*lis)


lim = 10 ** 5 + 1
isPrime = [True] * lim
p = []
for i in range(2, lim):
	if isPrime[i]:
		p.append(i)
		for j in range(i * i, lim, i):
			isPrime[j] = False
n = int(input())
facts = set()
for prime in p:
	if n % prime == 0:
		facts.add(prime)
ans = set()
prod = 1
for i in range(1, n):
	good = True
	for fact in facts:
		if i % fact == 0:
			good = False
			break
	if good:
		ans.add(i)
		prod = prod * i % n
if prod != 1:
	ans.remove(prod)
print(len(ans))
print(*sorted(ans))


from collections import Counter

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(1):
	n = int(input())
	coPrimes = []
	for i in range(1, n + 1):
		if gcd(n, i) == 1:
			coPrimes.append(i)
	p = 1
	for i in coPrimes:
		p = p * i % n
	if p == 1:
		print(len(coPrimes))
		print(*coPrimes)
	else:
		coPrimes.remove(p)
		print(len(coPrimes))
		print(*coPrimes)


try:
	import math
	n = int(input())
	op = []
	s = 1
	for i in range(1, n):
		if math.gcd(i, n) == 1:
			op.append(i)
			s = s * i % n
	if s != 1:
		op.remove(op[len(op) - 1])
	print(len(op))
	print(*op)
except:
	pass


import sys, functools, collections, bisect, math, heapq
import os
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().strip().split()))
arr = []
ans = 1
for i in range(1, n):
	if math.gcd(i, n) == 1:
		arr.append(i)
		ans *= i
		ans %= n
if ans != 1:
	arr.remove(ans)
	print(len(arr))
	print(' '.join((str(i) for i in arr)))
else:
	print(len(arr))
	print(' '.join((str(i) for i in arr)))


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
n = inp()

def prime_factorize(n):
	if n == 1:
		return [1]
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a
pr = list(set(prime_factorize(n)))
l = [0] * (n + 10)
for x in pr:
	for i in range(x, n + 5, x):
		l[i] = 1
res = []
for i in range(1, n):
	if l[i] == 0:
		res.append(i)
if res == [1]:
	print(1)
	print(1)
else:
	mul = 1
	for x in res:
		mul *= x
		mul %= n
	if mul == 1:
		print(len(res))
		print(*res)
	else:
		print(len(res) - 1)
		print(*res[:len(res) - 1])


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(1):
	(n,) = get_ints()
	a = []
	p = 1
	for i in range(1, n):
		if math.gcd(i, n) == 1:
			a.append(i)
			p = p * i % n
	if p != 1:
		tmp = []
		for i in range(len(a)):
			if a[i] != p:
				tmp.append(a[i])
		print(len(tmp))
		print(*tmp)
	else:
		print(len(a))
		print(*a)


import math

def solve():
	n = int(input())
	res = []
	prod = 1
	for i in range(1, n):
		if math.gcd(i, n) == 1:
			res.append(i)
			prod *= i
			prod = prod % n
	if prod == 1:
		print(len(res))
		print(*res)
	else:
		res.remove(res[-1])
		print(len(res))
		print(*res)
t = 1
while t > 0:
	t -= 1
	solve()


from math import gcd
n = int(input())
l = []
val = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		l.append(i)
		val = val * i
		val = val % n
if val == 1:
	print(len(l))
	print(*l)
else:
	l.pop()
	print(len(l))
	print(*l)


import math

def main():
	N = int(input())
	ans = []
	for i in range(1, N):
		if math.gcd(i, N) == 1:
			ans.append(i)
	mod = 1
	for i in ans:
		mod *= i
		mod %= N
	if mod != 1:
		ans.remove(mod)
	print(len(ans))
	print(*ans)
main()


def get_mod(n, r):
	c = 1
	for e in r:
		c = c * e % n
	return c

def solve(n):

	def factorize(n):
		v = []
		p = 2
		while n > 1:
			if n % p == 0:
				v.append(p)
				while n % p == 0:
					n //= p
			p += 1
		return v
	v = set(range(1, n))
	factors = factorize(n)
	for i in range(2, n):
		if any((i % x == 0 for x in factors)):
			v.discard(i)
	r = sorted(v)
	while True:
		m = get_mod(n, r)
		if m == 1:
			break
		r.remove(m)
	return r
n = int(input())
r = solve(n)
print(len(r))
print(' '.join((str(x) for x in r)))


import sys
import math
n = int(sys.stdin.readline())
ans = []
cnt = 1
for i in range(1, n):
	if math.gcd(i, n) == 1:
		cnt = cnt * i % n
		ans.append(i)
if cnt != 1:
	ans.pop()
print(len(ans))
print(*ans)


from math import gcd
n = int(input())
l = [0 for i in range(n)]
prod = 1
for i in range(n):
	if gcd(i, n) == 1:
		l[i] = 1
		prod = prod * i % n
if prod != 1:
	l[prod] = 0
print(l.count(1))
for i in range(n):
	if l[i] == 1:
		print(i, end=' ')


import math
n = int(input())
prod = 1
l = [1]
for k in range(2, n - 1):
	if math.gcd(n, k) == 1:
		prod = prod * k % n
		l.append(k)
if prod != 1:
	l.append(n - 1)
print(len(l))
print(' '.join(map(str, l)))


from math import gcd

def solve(n):
	li = [1]
	And = 1
	for i in range(2, n):
		if gcd(i, n) == 1:
			li.append(i)
			And = And * i % n
	if And != 1:
		li.pop()
	print(len(li))
	print(*li)
n = int(input())
solve(n)


import math

def read():
	n = int(input())
	solve2(n)

def solve(n):
	for i in range(2, 20):
		solve2(i)

def solve2(n):
	ans = [1]
	i = 2
	while i < n:
		if math.gcd(i, n) == 1:
			ans.append(i)
		i += 1
	d = dict()
	acc = 1
	for i in range(len(ans)):
		acc = acc * ans[i] % n
		d[acc] = i
	end = d[1] + 1
	print(end)
	print(*ans[:end])
read()


import time
from math import gcd
from functools import reduce
from operator import mul

def m(s, n):
	return reduce(lambda x, y: x * y % n, s)

def check(n):
	t = [x for x in range(1, n) if gcd(n, x) == 1]
	this = m(t, n)
	if this != 1:
		del t[t.index(this)]
	print(len(t))
	print(*t)
	assert m(t, n) == 1
n = int(input())
check(n)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def f(N):
	result = [1]
	p = 1
	for i in range(2, N):
		if gcd(i, N) == 1:
			p *= i
			p %= n
			if i == N - 1:
				if p % N == 1:
					result.append(i)
			else:
				result.append(i)
	return result
n = int(input())
ans = f(n)
h = len(ans)
print(len(ans))
for i in range(h):
	print(ans[i], end=' ')


from collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from sys import *
from re import *

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer):
	stdout.write(str(answer))
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
n = int(z())
prime = [1] * (n + 10)

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
prime = SieveOfEratosthenes(n + 10)

def coprime(a, b):
	if gcd(a, b) == 1:
		return True
	else:
		return False
res = 0
lst = []
p = 1
for i in range(1, n):
	if coprime(i, n):
		res += 1
		p *= i
		p %= n
		lst.append(i)
if p != 1:
	lst.remove(p)
print(len(lst))
print(*lst)


from math import gcd
n = int(input())
arr = []
p = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		arr.append(i)
		p *= i
		p %= n
if p != 1:
	arr.remove(p)
print(len(arr))
for i in arr:
	print(str(i), end=' ')


import math

def main():
	n = int(input())
	S = [a for a in range(1, n) if math.gcd(a, n) == 1]
	prod = 1
	for a in S:
		prod = prod * a % n
	if prod != 1:
		S.pop()
	print(len(S))
	print(' '.join((str(a) for a in S)))
main()


import math as mt
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
MAXN = 100001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
sieve()

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
n = inp()
count = 1
p = set(getFactorization(n))
d1 = [i for i in range(n)]
for i in range(2, n):
	for each in p:
		if i % each == 0:
			d1[i] = 1
ans = [1]
for i in range(2, n):
	if d1[i] != 1:
		ans.append(i)
ex = 1
for each in ans:
	ex = ex * each % n
if ex == 1:
	print(len(ans))
	print(*ans)
else:
	ans.remove(ex)
	print(len(ans))
	print(*ans)


def gcd(a, b):
	return a if not b else gcd(b, a % b)
n = int(input())
ans = []
prod = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		ans.append(i)
		prod = prod * i % n
if prod != 1:
	ans.remove(prod)
print(len(ans))
print(*ans)


import math
n = int(input())
l = [1]
for i in range(2, n + 1):
	if math.gcd(i, n) == 1:
		l.append(i)
x = len(l)
f = 0
prod = 1

def chk(l):
	prod = 1
	hi = 0
	for i in range(len(l)):
		prod *= l[i]
		prod = prod % n
		if prod == 1:
			hi = i
	return l[:hi + 1]
l = chk(l)
print(len(l))
print(*l)


from math import gcd
n = int(input())
ans = []
p = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		ans.append(i)
		p = p * i % n
if p == 1:
	print(len(ans))
	print(*ans)
else:
	print(len(ans) - 1)
	ans.remove(p)
	print(*ans)


from math import gcd
n = int(input())
ok = [0 for _ in range(n + 1)]
prod = 1
for i in range(1, n):
	if gcd(n, i) == 1:
		ok[i] = 1
		prod = prod * i % n
if prod != 1:
	ok[prod] = 0
print(sum(ok))
for i in range(0, n):
	if ok[i] == 1:
		print(i, end=' ')


import math
n = int(input())
prod = 1
ans = []
for num in range(1, n + 1):
	if math.gcd(num, n) == 1:
		prod = prod * num % n
		ans.append(num)
if prod != 1:
	ans.remove(prod)
ans = list(map(str, ans))
print(len(ans))
print(' '.join(ans))


from math import gcd
n = int(input())
res = [1]
t = 1
for i in range(2, n):
	if gcd(i, n) == 1:
		res.append(i)
		if i * i % n == 1:
			t = t * i % n
if t != 1:
	res.remove(t)
print(len(res))
print(*res, sep=' ')


import math
n = int(input())
tmp = []
product = 1
tool = 0
for i in range(n):
	if math.gcd(i, n) == 1:
		product *= i
		product = product % n
		tool += 1
		tmp.append(str(i))
if product == 1:
	print(tool)
	print(' '.join(tmp))
else:
	tmp.pop(tmp.index(str(product)))
	print(tool - 1)
	print(' '.join(tmp))


import heapq
import sys
from collections import *
from heapq import *
import math
import bisect

def input():
	return sys.stdin.readline()
n = int(input())
pr = 1
maxx = -1
cnt = 0
s = ''
ans = ''
for i in range(1, n):
	if math.gcd(i, n) == 1:
		pr = pr * i % n
		cnt += 1
		ans += str(i) + ' '
	if pr == 1:
		maxx = max(maxx, cnt)
		s += ans
		ans = ''
print(maxx)
print(s)


import math
n = int(input())
res = []
t = 1
for i in range(1, n):
	if math.gcd(i, n) == 1:
		res.append(i)
		t *= i
		t %= n
l = len(res)
if t == 1:
	print(l)
	print(*res)
else:
	print(l - 1)
	t = 0
	ans = []
	for i in res:
		if t >= l - 1:
			break
		ans.append(i)
		t += 1
	print(*ans)


from math import gcd
n = int(input())
product = 1
valid = [False] * n
for i in range(1, n):
	if gcd(n, i) == 1:
		valid[i] = True
		product = product * i % n
if product != 1:
	valid[product] = False
length = 0
for v in valid:
	if v:
		length += 1
print(length)
for i in range(1, n):
	if valid[i]:
		print(i, end=' ')
print()


from math import gcd
N = int(input())
ANS = []
X = 1
for i in range(1, N):
	if gcd(N, i) == 1:
		ANS.append(i)
		X = X * i % N
if X != 1:
	del ANS[ANS.index(X)]
print(len(ANS))
print(*ANS)


from math import gcd
n = int(input())
l = []
p = 1
for i in range(1, n):
	if gcd(n, i) == 1:
		p = p * i % n
		l.append(i)
if p != 1:
	l.pop()
print(len(l))
for i in l:
	print(i, end=' ')


from sys import stdin, stdout
from math import gcd
n = int(stdin.readline())
answer = 1
numbers = []
for i in range(1, n):
	if gcd(i, n) == 1:
		answer = answer * i % n
		numbers.append(str(i))
if answer == 1:
	stdout.write(str(len(numbers)) + '\n')
	stdout.write(' '.join(numbers) + '\n')
else:
	numbers.pop()
	stdout.write(str(len(numbers)) + '\n')
	stdout.write(' '.join(numbers) + '\n')


from sys import stdin, stdout
from math import gcd
input = stdin.readline

def main():
	t = 1
	for z in range(t):
		n = int(input())
		ar2 = [i for i in range(1, n) if gcd(n, i) == 1]
		n2 = len(ar2)
		ar = [0] * n2
		ar3 = [0] * n2
		num = 1
		for i in range(n2):
			num *= ar2[i]
			num %= n
			ar[i] = num
		if ar[-1] == 1:
			print(n2)
			print(*ar2)
			return
		else:
			print(n2 - 1)
			num = 1
			for i in range(n2 - 1, -1, -1):
				num *= ar2[i]
				num %= n
				ar3[i] = num
			od = -1
			for i in range(n2 - 2):
				if ar[i] * ar3[i + 2] % n == 1:
					od = i + 1
					break
			if od == -1:
				if ar[-2] == 1:
					od = n2 - 1
				else:
					od = 0
			for i in range(n2):
				if od != i:
					print(ar2[i], end=' ')
main()


import math

def primeFactors(n):
	while n % 2 == 0:
		(prim.append(2),)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			(prim.append(int(i)),)
			n = n / i
	if n > 2:
		prim.append(int(n))
prim = []
n = int(input())
ans = [1 for i in range(n + 1)]
primeFactors(n)
prim = list(set(prim))
prim.sort()
for i in prim:
	for j in range(i, n + 1, i):
		ans[j] = 0
an = 1
count = 0
arr = []
for i in range(1, n - 1):
	if ans[i] == 1:
		count += 1
		an = an * i % n
		arr.append(i)
if an * (n - 1) % n == 1:
	an = an * (n - 1) % n
	count += 1
	arr.append(n - 1)
if an != 1:
	print(-1)
print(count)
print(*arr)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	n = ii()
	p = 1
	x = []
	for i in range(1, n):
		if gcd(i, n) == 1:
			x.append(i)
			p *= i
			p %= n
	if p != 1:
		x.remove(p)
	print(len(x))
	print(*x)
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


import time
from math import gcd

def multiply_manual(n, iterable):
	prod = 1
	for x in iterable:
		prod *= x
		prod %= n
	return prod

def is_coprime(x, y):
	return gcd(x, y) == 1
n = int(input())
result = []
for i in range(1, n):
	if is_coprime(i, n):
		result.append(i)
prod = multiply_manual(n, result)
if prod != 1:
	result.remove(prod)
	result = [x for x in result if x != prod]
print(len(result))
print(' '.join(map(str, result)))


import math
n = int(input())
b = [1]
p = 1
for i in range(2, n):
	if math.gcd(i, n) == 1:
		b.append(i)
		p = p * i % n
if p % n == 1:
	print(len(b))
	print(*b)
else:
	b.remove(p)
	print(len(b))
	print(*b)


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
(test,) = Neo()
n = test
p = 1
Ans = 0
s = set()
for i in range(1, n):
	if math.gcd(n, i) == 1:
		p *= i
		p %= n
		s.add(i)
while p % n != 1:
	t = p % n
	p //= t
	s.discard(t)
print(len(s))
print(*sorted(s))


from collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from sys import *
from re import *

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer):
	stdout.write(str(answer))
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
lst = []
n = int(z())
res = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		lst.append(i)
		res *= i
		res %= n
if res % n != 1:
	del lst[lst.index(res % n)]
print(len(lst))
print(*lst)


n = int(input())
x = n
kek = set()
i = 2
while i * i <= n:
	while n % i == 0:
		kek.add(i)
		n //= i
	i += 1
if n != 1:
	kek.add(n)
ans = 0
num = 1
keku = 0
keke = []
bebe = []
for i in range(1, x):
	flag = True
	for elem in kek:
		if i % elem == 0:
			flag = False
			break
	if flag:
		keku += 1
		bebe.append(i)
		num *= i
		num %= x
		if num == 1:
			ans = keku
for i in range(ans):
	keke.append(bebe[i])
print(ans)
print(*keke)


import collections
import itertools
mod = 10 ** 9 + 7

def permutationbysum():
	for _ in range(int(input())):
		(num, l, r, achieve) = map(int, input().split())
		k = r - l + 1
		if k * (k + 1) // 2 <= achieve <= k * (num * 2 + 1 - k) // 2:
			outpos = r % num
			inpos = l - 1
			ans = [0] * num
			for i in range(num, 0, -1):
				if achieve - i > 0 or (achieve - i == 0 and inpos == r - 1):
					achieve -= i
					ans[inpos] = i
					inpos += 1
				else:
					ans[outpos] = i
					outpos += 1
					outpos %= num
			print(*ans)
		else:
			print(-1)

def peaks():
	for _ in range(int(input())):
		(num, peak) = map(int, input().split())
		pos = 1
		rpos = num
		ans = []
		now = 0
		if num == 1:
			if not peak:
				print(1)
			else:
				print(-1)
			continue
		if num == 2:
			if peak:
				print(-1)
			else:
				print(1, 2)
			continue
		added = 0
		while rpos + 1 != pos:
			if not peak:
				while pos <= rpos:
					ans.append(pos)
					pos += 1
				break
			if not now:
				ans.append(pos)
				pos += 1
			else:
				ans.append(rpos)
				rpos -= 1
				if num - added != 1:
					peak -= 1
			added += 1
			now = 1 - now
		if peak:
			print(-1)
			continue
		print(*ans)
import sys
input = sys.stdin.readline

def addone():
	for _ in range(int(input())):
		(num, changes) = input().split()
		l = collections.deque(sorted([int(i) for i in num]))
		perm = collections.deque()
		changes = int(changes)
		cd = 0
		ans = len(num)
		while True:
			nextnum = l.pop()
			while perm and perm[-1] == nextnum:
				l.append(perm.pop())
			c = 10 - nextnum - cd
			changes -= c
			cd += c
			if changes >= 0:
				if not c:
					perm.appendleft(1 - cd)
					l.appendleft(-cd)
				else:
					l.appendleft(1 - cd)
					l.appendleft(-cd)
				ans += 1
			else:
				break
		print(ans % 1000000007)
import math

def andsequences():

	def mapping(num):
		nonlocal mnum
		nonlocal c
		num = int(num)
		if num < mnum:
			mnum = num
			c = 1
		elif num == mnum:
			c += 1
		return num
	mod = 1000000007
	for _ in range(int(input())):
		mnum = float('inf')
		c = 0
		num = int(input())
		l = list(map(mapping, input().split()))
		for i in l:
			if mnum & i != mnum:
				print(0)
				break
		else:
			if c == 1:
				print(0)
			else:
				print(math.factorial(num - 2) * (c - 1) * c % mod)

def numberdigit():
	n = 10 ** 5 * 2
	l = [0] * 11
	mod = 10 ** 9 + 7
	l[0] = l[1] = l[2] = l[3] = l[4] = l[5] = l[6] = l[7] = l[8] = 2
	l[9] = 3
	l[10] = 4
	for i in range(11, n):
		l.append((l[i - 10] + l[i - 9]) % mod)
	for _ in range(int(input())):
		(num, c) = input().split()
		c = int(c)
		ans = 0
		for i in num:
			i = int(i)
			if 10 - i > c:
				ans += 1
			else:
				ans += l[c - (10 - i)]
		print(ans % mod)

def mushroom():
	(people, t1, t2, percent) = map(int, input().split())
	l = []
	percent = 1 - percent * 0.01
	for i in range(1, people + 1):
		(s, s1) = map(int, input().split())
		l.append([i, max(s * t1 * percent + s1 * t2, s1 * t1 * percent + s * t2)])
	l.sort(key=lambda x: x[1], reverse=True)
	for i in l:
		i[1] = '{:.2f}'.format(i[1])
		print(*i)

def escape():
	prins = int(input())
	dra = int(input())
	start = int(input())
	pack = int(input())
	c = int(input())
	speeddiff = dra - prins
	if speeddiff <= 0:
		return 0
	pd = start * prins
	ans = 0
	while pd < c:
		hs = pd / speeddiff
		pd += prins * hs
		if pd >= c:
			break
		time = pd / dra
		time += pack
		pd += prins * time
		ans += 1
	return ans

def perm():

	def high(n, k):
		return k * (2 * n - k + 1) // 2

	def low(k):
		return k * (k + 1) // 2
	for _ in range(int(input())):
		(num, lef, rig, s) = map(int, input().split())
		k = rig - lef + 1
		(rig, lef) = (rig - 1, lef - 1)
		if not high(num, k) >= s >= low(k):
			print(-1)
			continue
		l = [0] * num
		lp = lef
		rp = lef - 1
		for i in range(num, 0, -1):
			if high(i, k) >= s and s - i >= low(k - 1) and k:
				l[lp] = i
				lp += 1
				s -= i
				k -= 1
			else:
				l[rp] = i
				rp -= 1
		if k:
			print(-1)
		else:
			print(*l)

def newcom():
	for _ in range(int(input())):
		(days, price) = map(int, input().split())
		dl = input().split()
		worth = input().split()
		worth.append(0)
		ans = float('inf')
		req = 0
		left = 0
		for i in range(days):
			a = int(dl[i])
			w = int(worth[i])
			ans = min(ans, req + max(0, price - left + a - 1) // a)
			ns = max(0, w - left + a - 1) // a
			req += ns + 1
			left += a * ns - w
		print(ans)

def shorttask():
	num = 10000000
	l = [-1] * (num + 2)
	s = [-1] * (num + 2)
	l[1] = 1
	for i in range(2, int(math.sqrt(num + 1)) + 2):
		if l[i] == -1:
			l[i] = i
			for x in range(i * i, num + 1, i):
				if l[x] == -1:
					l[x] = i
	s[1] = 1
	for i in range(2, num + 1):
		if l[i] == -1:
			l[i] = i
			s[i] = i + 1
		else:
			i1 = i
			s[i] = 1
			while i1 % l[i] == 0:
				i1 /= l[i]
				s[i] = s[i] * l[i] + 1
			s[i] *= s[i1]
	ans = [-1] * (num + 1)
	for i in range(num, 0, -1):
		if s[i] < num:
			ans[s[i]] = i
	...

def perfectsq():
	for _ in range(int(input())):
		n = input()
		for i in input().split():
			sq = math.sqrt(int(i))
			if sq != int(sq):
				print('YES')
				break
		else:
			print('NO')

def comb(n, c):
	return math.factorial(n) // (math.factorial(c) * math.factorial(n - c))

def and0big():
	for _ in range(int(input())):
		(l, k) = map(int, input().split())
		print(l ** k % mod)

def mod1p():

	def gcd(x, y):
		if not x:
			return y
		if not y:
			return x
		return gcd(y, x % y)
	n = int(input())
	ans = []
	p = 1
	for i in range(1, n):
		if gcd(i, n) == 1:
			ans.append(i)
			p = p * i % n
	r = p % n
	if r == 1:
		print(len(ans))
		print(*ans)
	else:
		ans.remove(r)
		print(len(ans))
		print(*ans)
mod1p()


import sys
input = sys.stdin.readline

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		return 0
	else:
		return x % m
n = int(input())
a = [1]
b = []
for i in range(2, n):
	x = modinv(i, n)
	if x != 0:
		if x != i:
			a.append(i)
		else:
			b.append(i)
l = len(b)
if l > 1:
	a.extend(b)
	a.sort()
print(len(a))
print(*a)


from math import gcd
n = int(input())
a = [x for x in range(1, n) if gcd(n, x) == 1]
b = [x * x % n for x in a]
sq = b.count(1)
if sq == 2:
	a.remove(n - 1)
print(len(a))
print(*a)


def ld(n):
	i = 1
	p = n ** 0.5
	l = []
	while i <= p:
		if n % i == 0:
			if n / i == i:
				if i != 1:
					l.append(i)
			else:
				if i != 1:
					l.append(i)
				l.append(n // i)
		i = i + 1
	l.sort()
	return l
n = int(input())
stk = []
lis = ld(n)
h = len(lis)
for i in range(1, n):
	t = False
	for j in range(h):
		if i % lis[j] == 0:
			t = True
			break
	if not t:
		stk.append(i)
k = 1
for j in range(len(stk)):
	k *= stk[j]
	k %= n
lo = True
if k % n != 1:
	lo = False
h = len(stk)
if lo:
	print(h)
else:
	print(h - 1)
for i in range(h):
	if i == h - 1:
		if lo:
			print(stk[i], end=' ')
	else:
		print(stk[i], end=' ')


D = {}
q = 2
plist = []
while q < 100000:
	if q not in D:
		plist.append(q)
		D[q * q] = [q]
	else:
		for p in D[q]:
			D.setdefault(p + q, []).append(p)
		del D[q]
	q += 1
n = int(input())
a = [True for _ in range(n)]
a[0] = False
for p in plist:
	if n % p == 0:
		for x in range(p, n, p):
			a[x] = False
while True:
	result = 1
	for x in range(1, n):
		if a[x]:
			result = result * x % n
	if result == 1:
		break
	else:
		for x in range(n - 1, 0, -1):
			if a[x]:
				a[x] = False
				break
print(sum(a))
final = []
for x in range(1, n):
	if a[x]:
		final.append(x)
print(*final)


n = int(input())
import math
Coprime = []
for i in range(1, n):
	if math.gcd(i, n) == 1:
		Coprime.append(i)
ans = 1
for c in Coprime:
	ans *= c
	ans %= n
if ans == 1:
	print(len(Coprime))
	for c in Coprime:
		print(c, end=' ')
else:
	print(len(Coprime) - 1)
	for c in Coprime:
		if c == n - 1:
			continue
		print(c, end=' ')


from __future__ import print_function
from sys import stdin
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
ans = []
pro = 1
for i in range(1, n):
	if gcd(i, n) == 1:
		ans.append(i)
		pro = pro * i % n
if pro != 1:
	ans.pop()
print(len(ans))
print(*ans)


from math import gcd
n = int(input())
p = 1
t = []
for i in range(1, n):
	if gcd(i, n) == 1:
		t.append(i)
		s = p * i
		p = s % n
if p == 1:
	print(len(t))
	print(*t)
else:
	del t[-1]
	print(len(t))
	print(*t)


from math import gcd
n = int(input())
units = [x for x in range(1, n) if gcd(n, x) == 1]
prod = 1
for x in units:
	prod = x * prod % n
if prod != 1:
	units.remove(prod)
print(len(units))
print(*units)


import math
t = int(input())
p = []
m = 1
for i in range(1, t):
	if math.gcd(i, t) == 1:
		p.append(i)
		m = m * i % t
if m != 1:
	p.remove(p[len(p) - 1])
print(len(p))
print(' '.join((str(x) for x in p)))


from sys import stdin, stdout
input = stdin.readline

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
import math as mt
MAXN = 10 ** 5 + 5
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = set()
	while x != 1:
		ret.add(spf[x])
		if len(ret) == 2:
			return True
		x = x // spf[x]
	if len(ret) == 1:
		if 2 in ret:
			return True
		return False
	return True
sieve()
t = 1
for _ in range(t):
	n = int(input())
	vals = []
	for i in range(1, n - 1):
		if gcd(n, i) == 1:
			vals.append(i)
	if n == 2:
		vals.append(n - 1)
		stdout.write(str(len(vals)) + '\n')
		for i in vals:
			stdout.write(str(i) + ' ')
		stdout.write('\n')
		continue
	if n == 4:
		stdout.write(str(len(vals)) + '\n')
		for i in vals:
			stdout.write(str(i) + ' ')
		stdout.write('\n')
		continue
	if getFactorization(n):
		if n % 2:
			vals.append(n - 1)
		elif getFactorization(n // 2):
			vals.append(n - 1)
	stdout.write(str(len(vals)) + '\n')
	for i in vals:
		stdout.write(str(i) + ' ')
	stdout.write('\n')


import sys
from math import gcd
n = int(input())
ans = set()
cur = 1
for x in range(1, n + 1):
	if gcd(x, n) == 1:
		ans.add(x)
		cur = cur * x % n
if cur != 1:
	ans.remove(cur)
print(len(ans), *ans)


DEBUG = False
if DEBUG:
	input = open('input.txt', 'r').readline
import functools

def gdc(a, b):
	if b == 0:
		return a
	if a < b:
		return gdc(b, a)
	return gdc(b, a % b)
n = int(input())
if n == 2:
	print(1)
	print(1)
else:
	arr = [x for x in range(1, n - 1) if gdc(n, x) == 1 or x == 1]
	p = functools.reduce(lambda a, b: a * b % n, arr)
	if p == n - 1:
		arr.append(n - 1)
	if n != 2:
		print(len(arr))
		print(' '.join((str(x) for x in arr)))


import sys
from math import gcd
input = sys.stdin.readline

def rec(i, n, z):
	if z == 0:
		return None
	if i == n:
		if z == 1:
			return []
		return None
	a1 = rec(i + 1, n, z * i % n)
	if a1 is not None:
		a1.append(i)
	a2 = rec(i + 1, n, z)
	if a2 is not None and (a1 is None or len(a1) < len(a2)):
		a1 = a2
	return a1

def simple(n):
	return rec(1, n, 1)[::-1]

def smart(n):
	z = []
	m = 1
	for i in range(1, n):
		if gcd(i, n) == 1:
			z.append(i)
			m = m * i % n
	if m == 1:
		return z
	z.pop(z.index(m))
	return z

def solve():
	n = int(input())
	a = smart(n)
	print(len(a))
	print(' '.join(map(str, a)))
solve()


from math import gcd
import sys

def input():
	return sys.stdin.readline().rstrip()

def extgcd(a, b):
	if b == 0:
		return (1, 0, a)
	(q, r) = (a // b, a % b)
	(x, y, d) = extgcd(b, r)
	(s, t) = (y, x - q * y)
	return (s, t, d)
INF = 1 << 64

def modinv(a, m):
	(x, y, d) = extgcd(a, m)
	if d != 1:
		return INF
	return x

def slv():
	n = int(input())
	x = set([])
	product = 1
	for i in range(1, n + 1):
		if gcd(i, n) == 1:
			x.add(i)
			product *= i
			product %= n
	v = modinv(product, n) % n
	if v != 1:
		x.remove(v)
	x = list(x)
	x.sort()
	print(len(x))
	print(*x)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import *
from math import *

def main():
	n = ii1()
	ans = []
	for i in range(1, n):
		if gcd(i, n) == 1:
			ans.append(i)
	flag = True
	pro = 1
	for i in ans:
		pro *= i
		pro %= n
	if pro == 1:
		print(len(ans))
		print(*ans)
	else:
		ans.pop()
		print(len(ans))
		print(*ans)
main()


from math import gcd
n = int(input())
ans = []
check = []
prod = 1
for i in range(1, n):
	if gcd(n, i) == 1:
		prod = prod * i % n
		check.append(prod)
		ans.append(i)
while True:
	if check[-1] != 1:
		ans.pop()
		check.pop()
	else:
		break
print(len(ans))
print(*ans)


import math

def coprimes():
	global l, p
	for i in range(1, n):
		if math.gcd(n, i) == 1:
			l.append(i)
			p = p * i
			if p > n:
				p = p % n
	return l
n = int(input())
l = []
p = 1
coprimes()
if p != 1:
	l = l[:-1]
print(len(l))
print(*l)


from __future__ import print_function
from sys import stdin
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
import math
n = int(input())
a = []
p = i = 1
while i < n:
	if math.gcd(i, n) < 2:
		a += (i,)
		p = p * i % n
	i += 1
if p > 1:
	a.remove(p)
print(len(a), *a)


n = int(input())
primes = []
is_prime = [1] * (n + 1)
for i in range(2, n + 1):
	if is_prime[i]:
		for j in range(2 * i, n + 1, i):
			is_prime[j] = 0
		primes.append(i)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g == 1:
		return x % m
	return None
s = 1
ans = [1]
myprimes = []
orig_n = n
for p in primes:
	if n % p == 0:
		myprimes.append(p)
		while n % p == 0:
			n //= p
if n != 1:
	myprimes.append(n)
for i in range(2, orig_n):
	for p in myprimes:
		if i % p == 0:
			break
	else:
		ans.append(i)
cur = 1
for v in ans:
	cur *= v
	cur %= orig_n
if cur != 1:
	assert modinv(cur, orig_n) == cur
	ans.remove(modinv(cur, orig_n))
print(len(ans))
print(*ans)


from math import gcd
rr = lambda : input().strip()

def solve(n):
	present = [0] * n
	prod = 1
	for i in range(1, n):
		if gcd(i, n) == 1:
			present[i] = 1
			prod = prod * i % n
	if prod != 1:
		present[prod] = 0
	return present
n = int(rr())
ans = solve(n)
print(ans.count(1))
for i in range(n):
	if ans[i]:
		print(i, end=' ')


from math import gcd as gd
n = int(input())
a = []
p = 1
if n == 2:
	print(1)
	print(1)
else:
	for i in range(1, n):
		if gd(i, n) == 1:
			p = p * i % n
			if i == n - 1 and p % n == n - 1:
				pass
			else:
				a.append(i)
	print(len(a))
	print(' '.join(map(str, a)))


from math import gcd
n = int(input())
(a, p, ind) = ([], 1, 0)
for i in range(1, n):
	if gcd(i, n) == 1:
		a.append(i)
		p = p * i % n
if p != 1:
	a.remove(p)
print(len(a))
print(*a)


import time
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		return -1
	else:
		return x % m
from random import randint as ri

def solve():
	N = getInt()
	ans = [1]
	tmp = 1
	cands = []
	for j in range(2, N):
		if math.gcd(j, N) > 1:
			continue
		cands.append(j)
		tmp *= j
		tmp %= N
	if tmp == 1:
		ans += cands
	else:
		y = modinv(tmp, N)
		cands.remove(y)
		ans += cands
	ans.sort()
	print(len(ans))
	print(*ans)
	return
solve()


import math

def solve(n):
	ans = [1]
	p = 1
	for i in range(2, n):
		bandera = True
		if math.gcd(i, n) == 1:
			ans.append(i)
			p = p * i % n
	if p != 1:
		ans = ans[:-1]
	return ans
n = int(input())
ans = solve(n)
print(len(ans))
for i in ans[:-1]:
	print(str(i) + ' ', end='')
print(ans[-1])