[XRCOI Round 2] C. 永恒

ID: 18702

远端评测题

500ms

128MiB

难度: 9

上传者:

标签>

单位根反演

背景

你想知道夜晚流星的真相吗？哈哈，真相就是缥缈须臾的一瞬天光罢了。
那么，趁着一切还美好，就这样静止吧……去往永恒。

对于一个长度为 $n$ 的序列 $(a_1, \cdots, a_n)$ ，满足 $0 \le a_i \le m$ 。

我们称其是一个原神序列，当且仅当满足：

\sum_{i = 1}^n i \cdot a_i \equiv 0 \pmod n.

求有多少个序列是原神序列，对 $10^9+7$ 取模。

共 $T$ 组数据。

对于每组数据，一行两个数 $n, m$ 。

对于每组数据，表示答案。

2
2 1
5 4

2
625

原神序列有 $[0, 0], [0, 1]$ 这两种。

本题采用捆绑测试。

Subtask 编号	$n$	$m$	得分
$1$	$n \le 8$	$m \le 8$	$4$
$2$	$n \le 100$	$m \le 100$	$8$
$3$	$n \le 5 \cdot 10^3$	$m \le 5 \cdot 10^3$	$8$
$4$	$n \le 10^5$	$m \le 10^5$	$15$
$5$	$n \le 10^5$	无限制	$10$
$6$	无限制	$m \le 10^5$	$10$
$7$	$n \le 10^7$	$m \le 10^7$	$15$
$8$	无限制		$30$

对于 $100\%$ 的数据：保证 $1 \le T \le 5, 0 \le n, m \le 10^{13}$ 。