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 $ 取模

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

23
2005
346920481