1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.math.BigInteger;
import java.util.Scanner;
public class Main
{
    static Scanner I=new Scanner(System.in);
    public static void main(String[] args)
    {
        int N=I.nextInt();
        int[] ar = { 0, 1, 2, 3, 4, 5, 6, 9, 12, 16, 20, 27, 36, 48, 64, 81, 108, 144, 192, 256, 324, 432, 576, 768, 1024, 1296, 1728, 2304, 3072, 4096, 5184, 6912, 9216, 12288, 16384, 20736, 27648, 36864, 49152, 65536, 82944, 110592, 147456, 196608, 262144, 331776, 442368, 589824, 786432, 1048576 };
        if(N<ar.length)System.out.println(ar[N]);
        else{
            int mod=(N-45)%5;int div=(N-45)/5;
            int w=ar[45+mod];
            
            BigInteger big=new BigInteger("4").modPow(new BigInteger(div+""), new BigInteger("1000000007"));
            big=big.multiply(new BigInteger(w+"")).mod(new BigInteger("1000000007"));
            System.out.println(big.toString());
        }
        I.close();
    }
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX