a*b problem

Problem Description

标题是骗你进来的，题目内容对标题有稍加扩展 $a=1$，$b=x_1^{t_1}x_2^{t_2}...x_k^{t_k}$，$1\leq ab\leq n$ 其中$gcd(x_1,x_2,...,x_k)=1$ ，$x_i$为正整数 求满足以上条件的有序数对 $(x_1,x_2,...,x_k)$ 数量，答案对 $10^9+7$ 取模

Input

第一行有一个整数 $T$ ，代表数组组数 每组数据包含两行： 第一行输入两个数 $n$,$K$ 第二行输入 $K$ 个数，$t_1, t_2, ..., t_K$ $1\leq T\leq 3$ $1\leq n\leq 10^{10}$ $1\leq k\leq 10^5$ $1\leq t_i\leq 33$

Output

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

Sample Input

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

Sample Output

23
2005
346920481

Source

2024“钉耙编程”中国大学生算法设计超级联赛（2）