所有这类跳台阶问题，都可以考虑动态规划，考虑一步怎么到达
F(n)=F(n-2^m)+F(n-2^(m-1))+...+F(n-2^0),n>=2^m;
注意边界，F(0)=1。
然后就是对10e9+3求模了。

import java.util.Scanner;

public class Main {


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ints = new int[n];

        int[] dp = new int[1001];
        dp[0] = 1;
        for(int i = 1; i < 1001; i++){
            int temp = 1;
            while (temp <= i) {
                dp[i] += dp[i - temp];
                dp[i] = dp[i] % 1000000003;
                temp *= 2;
            }
        }
        for(int i = 0; i < n; i++){
            System.out.println(dp[sc.nextInt()]);
        }

    }
}