为了与顽皮的混乱制造者和平相处,贝西和农夫约翰计划种植一些花园,以补充玻维尼亚郁郁葱葱的草地。正如任何优秀的园艺家都知道的那样,他们种植的每个花园都必须有完全相同的花卉布置。最初,农夫约翰可以种植 n 种不同的花,其中有 1 种是第 i 种花。
在接下来的 q 天,Farmer John 将收到一批新品种的花朵。在 j 天,他将收到 cj 个相同品种的花,但其品种与 Farmer John 已经拥有的花不同。
农夫约翰知道奢侈与极简主义之间的正确平衡,他希望使用恰好 k 种花卉。此外,为了减少浪费,Farmer John 选择的 k 种花中的每一种花都必须种植在某个花园中。每个花园必须是相同的;也就是说,所选的 k 个物种中的每一个都应该在每个花园中拥有相同数量的花朵。由于农夫约翰是民族平等的支持者,他希望建造尽可能多的花园。
在这 q 天的每一天收到鲜花后,Farmer John 想知道他可以创建的花园的最大数量在 k 个物种的所有可能选择中的总和。由于这可能是一个很大的数字,因此您应该输出对 109 + 7 取模的结果。
输入
输入的第一行包含三个整数 n、k 和 q (1 ≤ k ≤ n ≤ 100 000, 1 ≤ q ≤ 100 000)。
输入的接下来 n 行的第 i (1 ≤ i ≤ n) 包含一个整数 ai (1 ≤ ai ≤ 1 000 000),即 Farmer John 最初拥有的第 i 种花的数量。
输入的接下来 q 行的第 j (1 ≤ j ≤ q) 包含一个整数 cj (1 ≤ cj ≤ 1 000 000),即 Farmer John 在 j 天收到的新物种的花数。
输出
每 q 天后,输出花园最大可能数量的总和,其中总和取 k 物种的所有可能选择,模 109 + 7。
示例
输入 #1
3 3 2 4 6 9 8 6
输出 #1
5 16
输入 #2
4 1 2 6 5 4 3 2 1
输出 #2
20 21
注意
在第一个示例中,第一天之后,Farmer John 每种类型的花都有 (4, 6, 9, 8) 种,并且 k = 3。
选择 (4, 6, 8) 让他建造 2 个花园,每个花园分别有 (2, 3, 4) 朵花。选择 (4, 6, 9)、(4, 9, 8) 和 (6, 9, 8) 只能让他建造一个花园,因为每个物种都无法平均划分成多少个花园。因此,k = 3 朵花的所有选择的总和是 2 + 1 + 1 + 1 = 5。
第二天之后,Farmer John 每朵花都有 (4, 6, 9, 8, 6) 朵。所有选项的总和为 1 + 2 + 2 + 1 + 1 + 2 + 2 + 3 + 1 + 1 = 16。
在第二个示例中,k = 1。农夫约翰用 x 朵花可以建造 x 个花园。因此,查询的答案是 6 + 5 + 4 + 3 + 2 = 20 和 6 + 5 + 4 + 3 + 2 + 1 = 21。