package question;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question1808 {
 public static void main(String[] args) {
 System.out.println(new Question1808().maxNiceDivisors(73));
 }
 static int M=1000_000_000+7;
 public int maxNiceDivisors(int primeFactors) {
 if (primeFactors==1) return 1;
 long res=1;
 int mod = primeFactors%3;
 if (mod==1) {
 primeFactors-=4;
 res*=4;
 } else if (mod==2) {
 primeFactors-=2;
 res*=2;
 }
 res*=pow(3, primeFactors/3);
 return (int)(res%M);
 }

 public int pow(long a, int x) {
 long p=1;
 while (x>0) {
 if ((x%2)==1) {
 p*=a;
 p%=M;
 }
 x>>=1;
 a*=a;
 a%=M;
 }
 return (int)p;
 }
}