#P2627. JZPKIL

    ID: 1682 传统题 1000ms 512MiB 尝试: 429 已通过: 77 难度: 9 上传者: 标签>CF2700省选/NOI-莫比乌斯反演自然数幂和公式狄利克雷卷积交换求和顺序Miller–RabinPollard–Rho快速乘防溢出阶乘逆元预处理模逆元快速幂

JZPKIL

题目描述

给定 n,x,yn, x, y,求

$$\sum_{i=1}^{n}\mathrm{gcd}(i,n)^x \mathrm{lcm}(i,n)^y \bmod (10^9+7)$$

输入格式

第一行,询问个数 TT。

下面 TT 行,每行三个整数 n,x,yn, x, y。

输出格式

TT 行,每行一个整数,表示相应的询问的答案

样例 #1

样例输入 #1

5
6 0 0
6 0 1
6 1 0
6 1 1
1000000000 50 50

样例输出 #1

6
66
15
126
393442025

提示

30%30\% 的数据,x=yx=y

另 30%30\% 的数据,n≤109,x,y≤100n \le 10^9, x, y \le 100

100% 100\% 的数据,$T \le 100, 1 \le n \le 10^{18}, 0 \le x, y \le 3000$

来源

2012集训队互测,by gyz