#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 10010;
const int MOD = 1000000007;
int T, n;
int a[N], p[N];

int main()
{
    p[0] = 1;
    for (int i = 1; i < N; i ++ ) p[i] = p[i - 1] * 2 % MOD;

    cin >> T;
    for(int t=1; t<=T; t++) {
        cin >> n;
        for(int i=0; i<n; i++) cin >> a[i];
        int ans = 0;

        for(int i=0; i<n; i++) {
            ans = (ans + (LL)a[i] * (p[i] - p[n-i-1])) % MOD;
        }
        printf("Case #%d: %d\n", t, ans);
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int T, n, p;

typedef long long LL;

int main()
{
    cin >> T;
    for(int t=1; t<=T; t++) {
        cin >> n >> p;
        vector<string> vs;
        for(int i=0; i<p; i++) {
            string s;
            cin >> s;
            vs.push_back(s);
        }
        sort(vs.begin(), vs.end());
        vector<string> real;
        for(int i=vs.size()-1; i>=0; i--) {
            bool can = true;
            for(int j=i-1; j>=0; j--) {
                if(vs[i].substr(0, vs[j].size()) == vs[j]) {
                    can = false;
                    break;
                }
            }
            if(can) real.push_back(vs[i]);
        }

        LL ans = 1ll << n;
        for(auto& s : real) {
            ans -= (1ll << (n-s.size()));
        }
        printf("Case #%d: %lld\n", t, ans);
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;
int n, k;
char g[N][N];
// 在前i行放置，且整体放置形成的数字为j的放置方案
int f[N][1<<N];

int main()
{
    while(scanf("%d %d", &n, &k), n > 0) {
        for(int i=1; i<=n; i++)
            scanf("%s", g[i]);

        int tot = 1 << n;

        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for(int i=1; i<=n; i++) {
            // j表明放置在哪一列
            for(int j=0; j<n; j++) {
                if(g[i][j] == '#') {
                    // 可以放置，遍历之前的状态
                    for(int t=0; t<tot; t++) {
                        // 二者不应有冲突
                        if(((t >> j) & 1) == 0) {
                            f[i][t | (1 << j)] += f[i-1][t];
                        }
                    }
                }
            }
            // 不放
            for(int t=0; t<tot; t++) {
                f[i][t] += f[i-1][t];
            }
        }
        int ans = 0;
        for(int i=0; i<tot; i++) {
            if(__builtin_popcount(i) == k) {
                ans += f[n][i];
            }
        }
        cout << ans << endl;
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 22;
int n, m;
char g[N][N];
int have[200];
int ans = 1;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, int cnt)
{
    ans = max(ans, cnt);
    for(int i=0; i<4; i++) {
        int xx = dx[i] + x;
        int yy = dy[i] + y;
        if(xx>=0 && xx<n && yy>=0 && yy<m) {
            if(have[g[xx][yy]] == 0) {
                have[g[xx][yy]] = 1;
                dfs(xx, yy, cnt+1);
                have[g[xx][yy]] = 0;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++)
        scanf("%s", g[i]);

    have[g[0][0]] = 1;
    dfs(0, 0, 1);
    cout << ans << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, a[N];

bool check(int mid)
{
    for(int i=1; i<=n; i++) {
        mid = 2 * mid - a[i];
        if(mid < 0) return false;
        if(mid >= N) return true;
    }
    return true;
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    int l=0, r=1e5+5;
    while(l < r) {
        int mid = l+r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
int n, k;
int a[N];
int L[N], R[N];

bool check(int mid)
{
    int cnt = 0, s = 0;
    for(int i=1; i<=n; i++) {
        if(a[i] > mid) return false;
        if(s+a[i] > mid) {
            s = a[i];
            cnt++;
        } else {
            s += a[i];
        }
    }
    if(s) cnt++;
    return cnt <= k;
}

int main()
{
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];

    int l=1, r=250000;
    while(l < r) {
        int mid = l+r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    // cout << l << endl;

    int s = a[n], t = k;
    R[k] = n;

    for(int i=n-1; i>=1; i--) {
        if(s+a[i] > l) {
            L[t] = i+1;
            s = a[i];
            t--;
            R[t] = i;
        } else {
            s += a[i];
        }
    }
    L[t] = 1;
    for(int i=1; i<=k; i++) cout << L[i] << ' ' << R[i] << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;
int f[M];

int main()
{
    int T;
    cin >> T;
    int a[N];

    for(int i=1; i<=100; i++) a[i] = i * i;
    memset(f, 0x3f, sizeof f);

    f[0] = 0;
    for(int i=1; i<M; i++) {
        for(int j=1; j<=100; j++) {
            if(i < a[j]) break;
            f[i] = min(f[i], f[i-a[j]] + 1);
        }
    }

    for(int t=1; t<=T; t++) {
        int x;
        cin >> x;
        printf("Case #%d: %d\n", t, f[x]);
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

bool cmp(string a, string b)
{
    unordered_set<char> A, B;
    for (auto c : a)
        if (c != ' ')
            A.insert(c);
    for (auto c : b)
        if (c != ' ' )
            B.insert(c);

    if (A.size() != B.size()) return A.size() > B.size();

    return a < b;
}

int main()
{
    int T;
    cin >> T;
    for(int i=1; i<=T; i++) {
        int n;
        cin >> n;
        string ans, s;
        int res = 0;
        getchar();
        while(n--) {
            getline(cin, s);
            if(cmp(s, ans)) ans = s;
        }
        cout << "Case #" << i << ": ";
        cout << ans << endl;
    }
    return 0;
}

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int>> ans;
        for(int i=1, j=1, res=1; i<=sum; i++) {
            while(res < sum) res += ++j;
            if(res == sum && j-i+1 > 1) {
                vector<int> t;
                for(int k=i; k<=j; k++) t.push_back(k);
                ans.push_back(t);
            }
            res -= i;
        }
        return ans;
    }
};

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 50010, M = 16;
int f[N][M], g[N][M];
int n, q;
int a[N];

void init()
{
    for(int len=0; (1<<len)<=n; len++) {
        for(int i=1; i<=n; i++) {
            if(i + (1<<len) - 1 > n) break;
            if(len == 0) {
                f[i][len] = a[i];
                g[i][len] = a[i];
            } else {
                f[i][len] = max(f[i][len-1], f[i+(1<<(len-1))][len-1]);
                g[i][len] = min(g[i][len-1], g[i+(1<<(len-1))][len-1]);
            }
        }
    }
}

int query(int l, int r)
{
    int len = r-l+1;
    int k = log(len) / log(2);
    if(k == 0) return 0;
    return max(f[l][k], f[r-(1<<k)+1][k]) - min(g[l][k], g[r-(1<<k)+1][k]);
}

int main()
{
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];

    init();

    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << endl;
    }

    return 0;
}