SPOJ WA, LOCKER - Magic of the locker

LOCKER - Magic of the locker

My Solution: 25439050 (ID)

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

  1. for 0 ans is 1
  2. for 1 ans is 1.
  3. any other number n … count the no. of 3s by d = (n/3) and remainder rem = (n%3) then if rem is 1 then increase rem by 3 , decrease d by 1 …for final answer… raised 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.:grinning: