现在你会听到 Baby Ehab 的第一句话:“给定一个整数 $$$n$$$,找到 $$$[1,2, \ldots, n-1]$$$ 的最长子序列,其乘积为 $$$1$$$ 模 $$$n$$$。”请解决问题。
如果可以通过删除一些(可能是全部)元素从 $$$a$$$ 获得 $$$b$$$,则序列 $$$b$$$ 是数组 $$$a$$$ 的子序列。空子序列的乘积等于$$$1$$$。
输入
唯一一行包含整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。
输出
第一行应包含一个整数,即最长子序列的长度。
第二行应包含子序列的元素,按升序排列。
如果有多个解决方案,您可以打印任意一个。
示例
输入 #1
5
输出 #1
3 1 2 3
输入 #2
8
输出 #2
4 1 3 5 7
注意
在第一个示例中,元素的乘积是 $$$6$$$,它与 $$$1$$$ 模 $$$5$$$ 一致。唯一较长的子序列是 $$$[1,2,3,4]$$$。其乘积为 $$$24$$$,与 $$$4$$$ 模 $$$5$$$ 一致。因此,答案是$$$[1,2,3]$$$。