public class bigadd {

    /**
     * @param args
     */
    //***********************兩個相等數(shù)相加**********************************88
    public static String add(String s){
        char c[]=s.toCharArray();
        for(int i=0;i<c.length/2;i++){
            char t=c[i];
            c[i]=c[c.length-1-i];
            c[c.length-1-i]=t;
        }
        int r[]=new int[c.length+1];
        int carry=0;
        for(int i=0;i<c.length;i++){
            int t=Integer.parseInt(c[i]+"")+Integer.parseInt(c[i]+"")+carry;
            carry=t/10;
            r[i]=t%10;
        }
        r[c.length]=carry;
        String sr;
        if(r[c.length]==0)
            sr="";
        else
            sr="1";
        for(int j=r.length-2;j>=0;j--){
            sr+=r[j];
        }
        return sr;
    }
    //*******************************兩個不同數(shù)相加*****************************************
    public static String adddif(String s1,String s2){
        char c1[] ;
        char c2[] ;
        if (s1.length() >= s2.length()) {
            c1 = s1.toCharArray();
            c2 = s2.toCharArray();
        }
        else{
            c2 = s1.toCharArray();
            c1 = s2.toCharArray();
        }
        for(int i=0;i<c1.length/2;i++){
            char t=c1[i];
            c1[i]=c1[c1.length-1-i];
            c1[c1.length-1-i]=t;
        }
        for(int i=0;i<c2.length/2;i++){
            char t=c2[i];
            c2[i]=c2[c2.length-1-i];
            c2[c2.length-1-i]=t;
        }
       
        int r[]=new int[c1.length+1];
        int carry=0;
        for(int i=0;i<c2.length;i++){
            int t=Integer.parseInt(c1[i]+"")+Integer.parseInt(c2[i]+"")+carry;
            carry=t/10;
            r[i]=t%10;
        }
        for(int i=c2.length;i<c1.length;i++){
            int t=Integer.parseInt(c1[i]+"")+carry;
            carry=t/10;
            r[i]=t%10;
        }
        r[c1.length]=carry;
        String sr;
        if(r[c1.length]==0)
            sr="";
        else
            sr="1";
        for(int j=r.length-2;j>=0;j--){
            sr+=r[j];
        }
        return sr;
    }
    //*************************求2的N次冪*********************************8
    public static String pow(int n){
        if(n==0)
            return "1";
        else if(n==1)
            return "2";
        else
            return add(pow(n-1));       
    }
   
    public static String sumpow(int p1,int n,int q){
        String sum="";
        String pre=pow(p1);
        for(int i=p1;i<=n;i=i+q){
            sum=adddif(sum,pre);
            for(int j=1;j<=2;j++)               
                pre=add(pre);
        }
        return sum;
    }
    //************************************相減***********************************
    public static String minus(String s1,String s2){
        char c1[] ;
        char c2[] ;
        if (s1.length() >= s2.length()) {
            c1 = s1.toCharArray();
            c2 = s2.toCharArray();
        }
        else{
            c2 = s1.toCharArray();
            c1 = s2.toCharArray();
        }
        for(int i=0;i<c1.length/2;i++){
            char t=c1[i];
            c1[i]=c1[c1.length-1-i];
            c1[c1.length-1-i]=t;
        }
        for(int i=0;i<c2.length/2;i++){
            char t=c2[i];
            c2[i]=c2[c2.length-1-i];
            c2[c2.length-1-i]=t;
        }
       
        int r[]=new int[c1.length];
        int carry=0;
        for(int i=0;i<c2.length;i++){
            int t=Integer.parseInt(c1[i]+"")-Integer.parseInt(c2[i]+"")-carry;
            if(t<0){
                r[i]=Integer.parseInt(c1[i]+"")-Integer.parseInt(c2[i]+"")+10-carry;
                carry=1;
            }
            else{
                r[i]=t;
                carry=0;
            }
        }
        for(int i=c2.length;i<c1.length;i++){
            int t=Integer.parseInt(c1[i]+"")-carry;
            if(t<0){
                carry=1;
                r[i]=9;
            }
            else{
                r[i]=t;
                carry=0;
            }
        }
        String str;
        if(r[c1.length-1]==0){
            str="";
        }
        else{
            str=""+r[c1.length-1];
        }
        for(int j=r.length-2;j>=0;j--){
            str+=r[j];
        }
        return str;
       
    }
    //**********************************減1****************************************
    public static String minus1(String s){
        char c[]=s.toCharArray();
        int i;
        for(i=0;i<c.length/2;i++){
            char t=c[i];
            c[i]=c[c.length-1-i];
            c[c.length-1-i]=t;
        }
        int t=0;
        for(i=0;i<c.length;i++){
            t=Integer.parseInt(c[i]+"");
            if(t>0){
                t=t-1;
                break;
            }           
        }
        c[i]=(t+"").charAt(0);
        System.out.println(t+" "+i);
        String str;
        if(c[c.length-1]=='0')
            str="";
        else
            str=c[c.length-1]+"";
       
        for(int j=c.length-2;j>=i;j--)
            str=str+c[j];
        for(int j=i-1;j>=0;j--)
            str+=9;
        return str;
    }
    //*************************************加1************************************
    public static String add1(String s){
        char c[]=s.toCharArray();
        int i;
        for(i=0;i<c.length/2;i++){
            char t=c[i];
            c[i]=c[c.length-1-i];
            c[c.length-1-i]=t;
        }
        int t=0;
        for(i=0;i<c.length;i++){
            t=Integer.parseInt(c[i]+"");
            if(t<9){
                t=t+1;
                break;
            }   
        }
        String str;
        if(i==c.length)
            str="1";
        else{
            c[i]=(t+"").charAt(0);
            str="";
        }
        for(int j=c.length-1;j>=i;j--)
            str=str+c[j];
        for(int j=i-1;j>=0;j--)
            str+=0;
        return str;
    }
   
    public static void main(String[] args) {
        // TODO 自動生成方法存根
        //System.out.println(pow(1000));
        //System.out.println(pow(999));
        //System.out.println(adddif(pow(999),pow(999)));
        //System.out.println(adddif("19","999"));
        System.out.println(sumpow((4-3),(1000-3),2));
        //System.out.println(minus(pow(1000),pow(999)));
        //System.out.println(add1(pow(1000)));
    }

}