首先我们将题面翻译成数学语言，即给定 $n,k(1\le k\le n\le 10^5$，求从 $n$ 个人里选 $k$ 个人，再从这 $k$ 个人里选出任意多个人，再从这任意多个人里选出一个人的方案数：

$$
\sum\limits_{i=1}^{k}\binom{n}{i}\cdot\sum\limits_{j=1}^{i}\binom{i}{j}\cdot j
$$

直接暴力算的话复杂度是 $O(Tnk)$ 的，显然超时，我们先考虑如何优化 $\sum\limits_{j=1}^{i}\binom{i}{j}\cdot j$ 这一部分。

这一部分看着有点眼熟，与组合计数中的这条公式十分相似：

$$
\sum\limits_{i=0}^{n}\binom{n}{i}=2^n
$$

即从 $n$ 个数里选出任意多个数，也就是每个数都可以选或不选，有 $2^n$ 中方法。而我们需要优化的式子只是在此基础上多乘了一个系数，能否将这个系数去掉？

再次利用组合计数的性质：

$$
\binom{n}{m}=\binom{n}{n-m}
$$

想起我们小学不知道几年级就学过的等差数列求和公式，其原理是将数列首尾配对后可以将数列化简为 $O(1)$ 可求的式子，同理我们也可以将这个多项式首尾配对：

$$
\begin{array}{l}
\ \ \ \ \sum\limits_{j=1}^{i}\binom{i}{j}\cdot j\\
=\sum\limits_{j=0}^{i}\binom{i}{j}\cdot j\\
=\frac{\sum\limits_{j=0}^{i}\binom{i}{j}\cdot j+\sum\limits_{j=0}^{i}\binom{i}{i-j}\cdot (i-j)}{2}\\
=\frac{\sum\limits_{j=0}^{i}\binom{i}{j}\cdot i}{2}\\
=\frac{i\cdot\sum\limits_{j=0}^{i}\binom{i}{j}}{2}\\
=\frac{i\cdot 2^i}{2}\\
=i\cdot 2^{i-1}
\end{array}
$$

于是我们成功利用小学不知道几年级学的数学知识将这个多项式化简为了 $O(1)$ 可求的式子。现在我们需要继续化简这个式子：

$$
\sum\limits_{i=1}^{k}\binom{n}{i}\cdot i\cdot 2^{i-1}
$$

~~翻遍小学课本似乎并没有能用的方法~~，但我们似乎漏掉了一个重要的条件：答案对 8388608 取模。为什么是这个奇怪的数，它是偶数不是质数，这意味着我们无法通过线性预处理值域中所有数的逆元 $O(1)$ 求组合数。在经历过 2025 竟然是 3 的倍数这件事后（某年某月某次区统考时的某道题）我觉得应该将模数质因数分解一下，发现它竟然是 $2^{23}$！

也就是说，当上式中的 $i\gt 23$ 时 $\binom{n}{i}\cdot i\cdot 2^{i-1}$ 会有 $2^{23}$ 这因子，那么在对 $2^{23}$ 取模后答案一定为 $0$。于是这个式子就可以被化简为：

$$
\sum\limits_{i=1}^{\min(k,23)}\binom{n}{i}\cdot i\cdot 2^{i-1}
$$

而我们又有通过递推求组合计数的方法，可以做到 $O(nm)$ 预处理组合计数且无需计算逆元，其中 $m$ 是上文计算出来的 23。

可以再预处理处 $2^0,2^1,\dots,2^{22}$，现在我们就可以在常数的复杂度下求出答案了。

AC code：

#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x<<':'<<(x)<<' '
#define dbe(x) cerr<<#x<<':'<<(x)<<endl
#define eb emplace_back
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
const int P=8388608;//2^23
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin>>t;
    vi m2(23);
    m2[0]=1;
    for(int i=1;i<=22;i++)m2[i]=m2[i-1]*2;//预处理2的整数次幂
    const int N=1e5;
    vector<vi>C(24,vi(N+1));
    C[0][1]=C[1][1]=1;
    for(int i=2;i<=N;i++){//预处理组合计数
        C[0][i]=1;
        for(int j=1;j<=23;j++){
            C[j][i]=(C[j][i-1]+C[j-1][i-1])%P;
        }
    }
    while(t--){
        int n,k;
        cin>>n>>k;
        int ans=0;
        for(int i=1;i<=min(k,23);i++){//根据推导出的公式计算答案
            ans=(ans+(ll)C[i][n]*i*m2[i-1])%P;
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x<<':'<<(x)<<' '
#define dbe(x) cerr<<#x<<':'<<(x)<<endl
#define eb emplace_back
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
const int P=8388608;//2^23
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin>>t;
    vi m2(23);
    m2[0]=1;
    for(int i=1;i<=22;i++)m2[i]=m2[i-1]*2;//预处理2的整数次幂
    const int N=1e5;
    vector<vi>C(24,vi(N+1));
    C[0][1]=C[1][1]=1;
    for(int i=2;i<=N;i++){//预处理组合计数
        C[0][i]=1;
        for(int j=1;j<=23;j++){
            C[j][i]=(C[j][i-1]+C[j-1][i-1])%P;
        }
    }
    while(t--){
        int n,k;
        cin>>n>>k;
        int ans=0;
        for(int i=1;i<=min(k,23);i++){//根据推导出的公式计算答案
            ans=(ans+(ll)C[i][n]*i*m2[i-1])%P;
        }
        cout<<ans<<endl;
    }
    return 0;
}