for (unsigned long long int i = 2; i<=100000000;i++){
    if (i%2==0) {
        x[i] =(3*x[i/2] + 2*x[(unsigned long long int)(i/4)])&1152921504606846975;
    }
    else{
        x[i] =(2*x[(i-1)/2] + 3*x[(unsigned long long int)((i-1)/4)])&1152921504606846975;
    }

 }//these code for listing
unsigned long long int xtrans(unsigned long long int k){
    if (k<=100000000)return x[k];
    unsigned long long int result;
    if (k%2==0) {
        result =(3*xtrans(k/2) + 2*xtrans((unsigned long long int)(k/4)))&1152921504606846975;
    }
    else{
        result =(2*xtrans((k-1)/2) + 3*xtrans((unsigned long long int)((k-1)/4)))&1152921504606846975;
    }
    return result;
}//These code for calculating x