光速幂是一种 $O(\sqrt{n})$ 预处理， $O(1)$ 查询求 $2^{k}$ 的算法

先与处理出 $2^{1}, 2^{2}, 2^{3}, ……, 2^{\sqrt{n}}$ 和 $2^{\sqrt{n}}, 2^{2*\sqrt{n}}, 2^{3*\sqrt{n}}, ……, 2^{(n-1)*\sqrt{n}}, 2^{n}$

再用上面这两组搭配相乘，形如 $2^{a} * 2^{b} = 2^{k}$

其中 $a$ 为 $\frac{k}{\sqrt{n}}$, $b$ 为 $k\mod{\sqrt{n}}$，且 $a+b=k$

void init_quick_pow() {
    siz = sqrt(n) + 1; // sqrt有常数，要先记录下来
    pow1[0] = pow2[0] = 1;
    for (int i = 1; i <= siz; i++)
        pow1[i] = pow1[i - 1] * 2 % mod;
    for (int i = 1; i <= siz; i++)
        pow2[i] = pow2[i - 1] * pow1[siz] % mod;
}

int query(int k) { return pow1[k % siz] * pow2[k / siz] % mod; }