题解 | #魔法深渊#python动态规划

import math
m=int(input())
for _ in range(m):
    n=int(input())
    if n<4:
        print(n) # 小于4层时直接输出
    else:
        l=[1,2] # n以内2的整数次幂，初始化2个，随后续动态规划而添加
        dp=[1]*n
        dp[1],dp[2]=2,3
        for i in range(3,n):
            a=0
            for j in l:
                a+=dp[i-j] # 最后一步爬j层时，剩余层数的方法数
            if math.log(i+1,2)%1==0: # 通过对数、模判断i+1是否为2的整数次幂
                dp[i]=a+1 # 2的整数次幂，可一步爬出，所以+1
                l.append(i+1) # 将i+1加入到2的整数次幂列表中
            else:
                dp[i]=a
        print(dp[n-1]%(10**9+3))