Misinterpretation  Problem code: MISINTER

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Chef's brother likes to put words in Chef's mouth.
Chef hates it about him of course.
He has decided to become extremely careful about what he speaks.
Fortunately, he knows how his brother transforms the words, that Chef uses.
He has decided to use only those words which remain the same even after his brother's transformation!

If Chef speaks an N letter word, his brother moves all the letters which are at even positions (assuming, numbering of positions starts from 1), to the beginning of the word; and the rest of the letters follow as they appeared in the word. Eg. abdef becomes beadf; cdcd becomes ddcc.

Chef wants to know how many words can he use, provided that each word is composed of exactly N lowercase letters of the English alphabet. They use an ancient language in Byteland, which allows all possible words within the above definition!

Input format

The first line contains the number T, the number of test cases. In the following lines, T test cases follow. Every test case is a single line, that contains a single positive integer, N,
which is the length of the words that Chef wants to use.

Output format

For each test case, print the number of words of length N that Chef can use; that is, number of words, which remain the same after brother's transformation.
Since the result can be quite large, output the result modulo 1000000007.

Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 100000

Sample input

3
1
14
45

Sample output

26
456976
827063120

Let us explain this question with an example

   Suppose chef says 

                                1  2   3   4   5   6   7    8    9

The brother will misinterpret it as

                               2   4   6    8   1   3  5   7     9

So we can se that few of them needs to be in cycles 

here according the example 

1=2=4=8=7=5=1      (here as 1 comes up so the cycle gets repeated)

again

3=6   

SO there are only 2 cycles. IN other words there are two sscs.

So, the ans   26^cnt

where cnt is the number of sscs.

Though I couldnot understand why this solution dint pass with a dfs but  here is the solution

#include<bits/stdc++.h>
using namespace std;
int vis[100010];

int p[100010];
int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  memset(vis,0,sizeof(vis));
  int n;
  scanf("%d",&n);
  
  int f=1;
  for(int i=2;i<=n;i+=2)
  {
   p[f++]=i;
  }
  for(int i=1;i<=n;i+=2)
  {
   p[f++]=i;
  }
  int cnt=0;
  for(int i=1;i<=n;i++)
  {
       int val=i;
       if(!vis[i])
       {
                   cnt++;
    while(!vis[val])
    {
          vis[val]=1;
          val=p[val];
           
    }
    }
 }
         long long int ans=1; 
  for(int i=1;i<=cnt;i++)
  {
   ans=(ans*26)%1000000007;
  }
  
  cout<<ans<<endl;
 }
 return 0;
}