1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 const LL mod = 1e9 + 7; 8 LL p[66], f[66][2][2], g[66][2][2]; 9 int nn[66];10 11 LL cal(int len)12 {13     memset(f, 0, sizeof(f));14     memset(g, 0, sizeof(g));15     f[0][1][1] = 1;16     for(int i = 0; i < len; i++)17     for(int p = 0; p <= 1; p++)18     for(int q = 0; q <= 1; q++)19     {20         if(!f[i][p][q]) continue;21         for(int nl = 0; nl <= 1; nl++)22         for(int nr = 0; nr <= 1; nr++)23         {24             if(p && nl > nr) continue;25             if(q && nr > nn[i+1]) continue;26             int np = p && nl == nr;27             int nq = q && nr == nn[i+1];28             f[i+1][np][nq] = (f[i+1][np][nq] + f[i][p][q]) % mod;29             if(!np) g[i+1][np][nq] = (g[i+1][np][nq] + g[i][p][q] + f[i][p][q] * (nl + nr)) % mod;30         }31     }32     return (g[len][0][0] + g[len][0][1]) % mod;33 }34 35 int main(void)36 {37     p[0] = 1LL;38     for(int i = 1; i < 66; i++) p[i] = p[i-1] * 2 % mod;39     int T;40     scanf("%d", &T);41     for(int kase = 1; kase <= T; kase++)42     {43         LL n;44         scanf("%lld", &n);45         int len = 0;46         while(n)47         {48             nn[++len] = n % 2;49             n /= 2;50         }51         reverse(nn + 1, nn + 1 + len);52         printf("Case #%d: %lld\n", kase, cal(len));53     }54     return 0;55 }