首先考察题目给出的 $\text{T.M.}$ 序列的性质。

通过观察，我们可以得到如下性质：

:::info[性质 1]

设 $S(k)$ 表示 $T_0$ 到 $T_{2^k-1}$ 项拼接起来构成的字符串。

$\operatorname{flip}(s)$ 表示 $01$ 串 $s$ 每一位取反（$1$ 变 $0$，$0$ 变 $1$）后的结果。

则 $S(k+1)=S(k)+\operatorname{flip}(S(k))$，其中加号表示字符串拼接。

证明可以使用归纳法，这里不赘述。

:::

:::info[性质 2]

$T_{2k}\neq T_{2k+1}$，可以直接用递推式证。

:::

:::info[性质 3]

在 $S(k)$ 的每一个 $0$ 后面插入一个 $1$，每个 $1$ 后面插入一个 $0$，此时得到的字符串是 $S(k+1)$。

:::

其中，性质 3 的正确打开方式是解题的关键，因为反过来用这一个性质可以启示我们递归求解，而性质 3 实际上就是一种递归方法。

先思考 $k=0$ 时如何递归。

:::info[递归方式]

如果 $|S|$ 为偶数，那么有如下两种递归方式：

• $S_{2k+1},S_{2k+2}$ 分一组，如果有一组全 $1$ 或全 $0$ 报告不合法，否则用 $S_{2k+1}$ 来指代这一组的信息。

• 加入两个新字符 $S_0=\operatorname{flip}(S_1),S_{|S|+1}=\operatorname{flip}(S_{|S|})$，这样就可以按照上文的方式两两分组然后递归了。（加入字符的目的就是为了凑出两两分组的形式，这样就可以递归计算了）

如果 $|S|$ 为奇数，那么此时也有两种递归方式：

• 加入新字符 $S_0=\operatorname{flip}(S_1)$，按上文的方式分组递归。

• 加入新字符 $S_{|S|+1}=\operatorname{flip}(S_{|S|})$，按上文的方式分组递归。

:::

我们可以发现 $T_{4k+1}=T_{4k+2}$（证明可以用归纳法），这样就可以说明对于一个长度大于 $4$ 的合法字符串 $S$ 而言，其内部必然存在连续的 $00$ 或 $11$，可以由此推得递归方式唯一。

对于长度不大于 $4$ 的情况，我们可以直接特判或者打表。

这个做法可以推广到 $k>0$ 的情况，只需要额外在递归时维护有多少个位置目前不受限制即可（本质相当于维护 $k$）。

需要注意的是，此时我们要在 $|S|+k\le 4$ 时特殊处理。

因为每次递归 $|S|+k$ 和 $|S|$ 减半，所以总状态数是 $O(\log (k+|S|))$，使用记忆化搜索的方式实现可以做到单次询问 $O(|S|+\log^2 k)$ 或 $O(|S|+\log k)$。

:::info[代码]

#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
using namespace std;
const int N=1e5+10,mod=1e9+9;
bool Mbg;
map<pair<string,ll>,int> mp;
void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;}
int solve(string str,ll k){
    if(str.length()+k<=4){
        if(str[0]=='1')
            for(auto &ch:str) ch='0'+'1'-ch;
        if(str.length()==1){
            if(k<=2) return k+1;
            else return 5;
        }else if(str.length()==2){
            if(str=="00") return max(1ll,k);
            else return k+1;
        }else if(str.length()==3){
            if(str=="000") return 0;
            else if(str=="011") return 1;
            else return k+1;
        }else{
            if(str[1]=='0') return (str[2]=='1');
            else return (str[2]!='1')||(str[3]!='1'); 
        }
    }else{
        if(mp.count(mk(str,k))) return mp[mk(str,k)];
        int res=0;bool ok;string tmp;
        ok=1;tmp="";
        for(int i=0;i+1<str.length();i+=2){
            if(str[i]==str[i+1]) ok=0;
            else tmp+=str[i];
        }
        if(ok){
            if(str.length()&1){
                tmp+=str.back();
                Add(res,solve(tmp,k/2));
            }else{
                Add(res,solve(tmp,(k+1)/2));
            }
        }
        ok=1;tmp="";tmp+=(char)('0'+'1'-str.front());
        for(int i=1;i+1<str.length();i+=2){
            if(str[i]==str[i+1]) ok=0;
            else tmp+=str[i];
        }
        if(ok){
            if(str.length()&1){
                Add(res,solve(tmp,(k+1)/2));
            }else{
                tmp+=str.back();
                Add(res,solve(tmp,k/2));
            }
        }
        return mp[mk(str,k)]=res;
    }
}
string str;ll k;
bool Med;
void slv(){
    cin>>str>>k;
    cout<<solve(str,k)<<'\n';
}
int main(){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    int t=1;cin>>t;
    while(t--) slv();
    cerr<<clock()*1.0/CLOCKS_PER_SEC<<' '<<(&Mbg-&Med)/1048576.0<<endl;
    return 0;
}

:::

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 9;
map<ll, int> dp;
ll calcdp(ll k)
{
    if (dp.count(k))
        return dp[k];

    if (k == 0)
        return dp[k] = 1;

    if (k == 1)
        return dp[k] = 2;

    if (k == 2)
        return dp[k] = 3;

    calcdp((k + 1) >> 1), calcdp(k >> 1);
    return dp[k] = (dp[(k + 1) >> 1] + dp[k >> 1]) % mod;
}
ll calcans(string S, ll k)
{
    if (S.length() == 1)
        return calcdp(k);

    if (k + S.length() <= 3)
    {
        if (k == 0)
        {
            if (S == "000" || S == "111")
                return 0;

            return 1;
        }

        if (k == 1)
        {
            if (S == "00" || S == "11")
                return 1;

            return 2;
        }

        return calcdp(k);
    }

    string T = "";
    ll res = 0;
    int flg = 1;

    for (int i = 0; i < S.length() && flg; i += 2)
    {
        if (i + 1 < S.length() && S[i] == S[i + 1])
            flg = 0;

        T += S[i];
    }

    if (flg /*&& k-(S.length()&1)>=0*/)
        res = (res + calcans(T, (k - (S.length() & 1) + 1) >> 1)) % mod;

    flg = 1;
    T = "";
    T += ('0' + '1' - S[0]);

    for (int i = 1; i < S.length() && flg; i += 2)
    {
        if (i + 1 < S.length() && S[i] == S[i + 1])
            flg = 0;

        T += S[i];
    }

    if (flg /*&& k-(S.length()-1&1)>=0*/)
        res = (res + calcans(T, (k - ((S.length() - 1) & 1) + 1) >> 1)) % mod;

    return res;
}
string S;
ll k;
int main()
{
    int T;cin >> T;
    while (T--)
    {
        cin >> S >> k;
        cout << calcans(S, k) << endl;
        dp.clear();
    }
    return 0;
}