给定 $n,a,b,p$（$p$ 不一定是质数），求：
$$$\sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor} a^i b^{n-2i} {n\choose 2i}$$$
对 $p$ 取模的结果。
有 $T$ 组询问。
提示：推荐使用 C++，且使用 C++ 的参赛者可以用__int128_t进行 128 位元的大整数运算，详细使用方式请自行百度。
__int128_t
第一行一个整数 $T~(1 \le T \le 10\,000)$，表示询问组数。
接下来 $T$ 行，每行四个整数 $n,a,b,p~(1 \le n,a,b,p \le 10^{18})$，表示一组询问。
共输出 $T$ 行，每行一个非负整数依序代表对应的询问的答案。
2 2 3 5 8 3 6 8 10
4 6
Comet OJ