[HOJ] 71 - 上帝的恩賜

#include<stdio.h>
#define m 2076030
long long int bi(long long int k){
    if(k==1) return 2;
    long long int tmp=bi(k/2);
    if(k%2) return tmp*tmp*2%m;
    return tmp*tmp%m;
}
int main(){
    long long int n;
    scanf("%lld",&n);
    printf("%lld\n",bi(n));
}