「Nhk R2」熊与二进制

题号：NC259923
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld

题目描述

定义函数 $f(i)$ 为二进制下 $g(i)$ 数位上 $1$ 的个数， $g(i)=i\oplus (i-1)$ ，其中 $\oplus$ 表示按位异或。

请求出 $\left(\displaystyle\sum_{i=1}^{2^n-1}\binom n{f_i}\right)\bmod p$ 和 $\left(\displaystyle\sum_{i=1}^{2^n-1}f_ig_i\binom n{f_i}\right)\bmod p$ 。

输入描述:

⚠：本题为多组输入。

第一行一个正整数 ，表示数据组数。

对于每组数据，输入两个正整数 ，。

输出描述:

输出共  行，每行两个整数，表示答案。

示例1

输入

复制

3
1 998244353
15 998244353
114514 998244353

输出

复制

1 1
14316139 993608674
985298479 346037567

备注:

对于所有数据，，，。