题目描述

标题是骗你进来的，题目内容对标题有稍加扩展

$a=1，b=x_1^{t_1}x_2^{t_2}...x_k^{t_k}，1≤ab≤n$

其中 $\gcd(x_1,x_2,...,x_k)=1$ ，$x_i$为正整数

求满足以上条件的有序数对 $(x_1,x_2,...,x_k)$ 数量，答案对 $10^9+7$ 取模

输入格式

第一行有一个整数 $T$（$1≤T≤3$） ，代表数组组数

每组数据包含两行：

第一行输入两个数 $n,K$（$1≤n≤10^{10},1≤k≤10^5$）

第二行输入 $K$ 个数，$t_1,t_2,...,t_K$（$1≤t_i≤33$）

输出格式

有序数对 $(x_1,x_2,...,x_k)$ 数量，答案对 $10^9+7$ 取模

输入样例

3
10 2
1 1
1000 4
1 2 3 4
10000000000 6
2 3 2 1 1 4

输出样例

23
2005
346920481