#PQJ41x4264. QOJ 41_4264

    ID: 2962 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:集训队互测 2015组合数学

QOJ 41_4264

标题: 普罗达科特 - Problem - QOJ.ac

#4264. 普罗达科特

Statistics

The problem was used in the following contests:

令 N=∏ni=1paii,M=∏ni=1pbii,其中 pi 是两两不同的素数。

求将 N 表示成 k 个正整数的乘积的方案数,也就是 N=∏ki=1xi 的解的个数,答案对 109+21 取模。

对于子问题 1,要求对于所有整数 i 满足 1≤i<k,都有 xi<xi+1。

对于子问题 2,要求对于所有整数 i 满足 1≤i<k,都有 xi≤xi+1。

对于两个子问题都要求对于所有整数 i 满足 1≤i≤k 都有 xi∤M,即 xi 不是 M 的约数。

输入格式

第一行两个正整数 n,k。

接下来一行 n 个非负整数,第 i 个整数表示 ai。

接下来一行 n 个非负整数,第 i 个整数表示 bi。

输入中没有给出 p1,…,pn,显然 pi 的取值并不影响答案。

输出格式

一行两个整数,分别表示子问题 1 和 2 的答案。

样例一

input

5 3
5 5 4 5 5
3 0 3 2 3


output

295164 295326


样例二

input

10 5
13 11 17 7 9 2 11 11 10 12
7 9 4 15 18 4 9 7 4 2


output

75340090 59089865


限制与约定

共 10 个测试点,只有子问题 1 答案正确将获得 3 分,只有子问题 2 答案正确将获得 6 分,都正确将获得 10 分。

测试点编号 n ai bi k 1≤5≤5≤5≤32≤10≤20≤20≤53=1≤1018≤1018≤254≤50≤103=0≤205≤1018≤256≤103≤103≤107≤1018≤1018≤108≤159≤2010≤25

**时间限制:**3s

**空间限制:**256MB

来源

中国国家集训队互测2015 - By 杜瑜皓