C. Product 1 Modulo N-Codeforces Round ＃716 (Div. 2)

Problem - 1514C - Codeforces

C. Product 1 Modulo N

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

Input

The only line contains the integer nn (2≤n≤1052≤n≤105).

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

Copy

5

output

Copy

3
1 2 3 

input

Copy

8

output

Copy

4
1 3 5 7 

Note

In the first example, the product of the elements is 66 which is congruent to 11 modulo 55. The only longer subsequence is [1,2,3,4][1,2,3,4]. Its product is 2424 which is congruent to 44 modulo 55. Hence, the answer is [1,2,3][1,2,3].

=========================================================================

First pair 50 All numbers within dfs I found that the selected numbers are all coprime numbers , The only difference is , Some figures have been chosen n-1 Some have no choice , We can judge the product of all coprime numbers , If it is 1, Then output the answer directly , Otherwise, remove one n-1 Output the rest .

# include<iostream>
# include<algorithm>
# include<math.h>
# include<queue>

using namespace std;
typedef long long int ll;

int ans[1000000+10];

int main()
{


   int n;

   cin>>n;

   int len=1;


   ll sum=1;

   for(int i=1;i<n;i++)
   {
       if(__gcd(i,n)==1)
       {

           ans[len]=i;


           sum*=i;
           sum%=n;

           len++;

       }
   }

   if(sum==1)
    {

         cout<<len-1<<endl;

         for(int i=1;i<=len-1;i++)
            {
                cout<<ans[i]<<" ";
            }
      }
      else
      {
          cout<<len-2<<endl;

          ll temp=1;

          for(int i=1;i<=len-2;i++)
          {
              cout<<ans[i]<<" ";

              temp*=ans[i];



          }


      }





    return 0;

}