Hi, I have already been through the discussions on this question on SPOJ…can’t reach an AC tho!!

My approach:

- for 0 ans is 1
- for 1 ans is 1.
- any other number
**n**… count the no. of 3s by**d = (n/3)**and remainder**rem = (n%3)**then*if*…for final answer… raised**rem is 1**then**increase rem by 3**,**decrease d by 1****3^d**and**multiply with rem**.

Code:

import java.io.*;

```
class Main {
static long c = (long)(Math.pow(10,9)+7);
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int l = Integer.parseInt(br.readLine());
while (l-- > 0) {
long n = Long.parseLong(br.readLine());
long res = 1;
if(n==1){System.out.println(1);continue;}
long d = ((n%c)/3)%c;
long rem = (n%3);
if(rem == 1){d--;rem+=3;}
else if(rem == 0){rem++;} // keeps final ansr non-zero
long a = 3;
while (d > 0) {
if ((d & 1) == 1) {
res = (res*a)%c;
}
a = (a*a)%c;
d >>= 1;
}
res = (rem*res);
System.out.println(res);
}
}
}
```

PS: This is my first time asking a doubt … Any test case where my code fails will also help. Thank you.