题号：NC229747
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
定义函数
)
：
- 在
时，为满足
且
%3D1)
的有序对
)
个数；
- 在
时，
%3D%5Csum_%7Bu%5Ccdot%20v%3Dn%7D%5Cfrac%7Bf_%7Br-1%7D(u)%2Bf_%7Br-1%7D(v)%7D%7B2%7D)
。
一共
组询问，每组询问给出
，求
模
的结果。
输入描述:
第一行包括一个正整数)
。
接下来
行，每行包括两个整数)
。
输出描述:
输出一个整数表示答案。
示例1
输入
复制
5
0 30
1 25
3 65
2 5
4 48
备注:
原题链接：https://codeforces.com/problemset/problem/757/E