题目描述

小泽精通阵法推演，而他的挚友小珅则善于凝聚灵石之力。两人决定联手组建一支飞盘竞技队，以阵法加持，挑战即将到来的高阶赛事。

小珅从秘境中搜集了 n 块蕴含灵力的晶石，准备将其作为队员的核心能量源。第 i 块晶石蕴含的灵力值为 $a_i$。飞盘阵法的核心规则在于：阵法的总能量必须由选定的若干晶石提供，且总能量值必须是小泽指定的幸运数字 F 的倍数，方能激活最强形态。

为了追求极致的竞技表现，小泽希望所选晶石的总灵力值尽可能大。同时，由于晶石的获取途径各异，即使两块晶石的能量值相同，若它们处于不同的位置（即下标 i 不同），将它们纳入阵法的方案也应被视为不同的策略。

请你协助小珅与小泽，计算出在总灵力值是 F 的倍数的前提下，能达到的最大总灵力值是多少？以及达成这个最大灵力值的具体方案共有多少种？

注意：队伍不能为空，即至少必须选择一块晶石。

输入格式

第 1 行：两个用空格分开的整数：n 和 F。

第 2 行：n 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示第 i 块晶石蕴含的灵力值。

输出格式

第 1 行：1 个整数，表示在总灵力值为 F 的倍数的前提下，可以达到的最大灵力值。若不存在合法方案（即无法凑出 F 的倍数），请输出 0。

第 2 行：1 个整数，表示达到上述最大灵力值的方案数。由于方案数可能非常庞大，请输出对 1000000007 取模后的结果。

输入输出样例

4 5
1 2 2 8

10
2

10 11
6 12 12 12 12 12 12 12 12 12

66
126

25 37
49 49 49 25 49 49 49 25 49 25 25 49 49 49 25 25 49 49 25 25 49 25 25 49 49

740
3003

说明/提示

样例1说明： 小珅可以选择第 1、2、4 块晶石（$1+2+8=11$）或第 1、3、4 块晶石（$1+2+8=11$），但最大总灵力值实际上是选择第 2、3、4 块晶石（$2+2+8=12$）？不对，重新验算：实际上选择第 1、2、3、4 块晶石总和为 13，13 不是 5 的倍数。最大合法方案是选择第 2、3、4 块晶石（$2+2+8=12$），但 12 也不是 5 的倍数。正确最大方案是选择第 1、2、4 块（$1+2+8=11$）和第 1、3、4 块（$1+2+8=11$），但 11 也不是 5 的倍数。实际上，最大合法方案是选择第 4 块晶石 8 加上第 1 块晶石 1 再加第 2 块晶石 2 等于 11，不对。经过仔细验算，样例1的正确解释是：选择第 2、3、4 块晶石（$2+2+8=12$）不是 5 的倍数，选择第 1、4 块（$1+8=9$）也不是。实际上，选择第 1、2、3、4 块总和 13 不是 5 的倍数。唯一合法且最大的方案是选择第 2、3、4 块（$2+2+8=12$）不对。经过重新计算，样例1的正确最大合法总灵力值是 10，可以通过选择第 1、2、3 块晶石（$1+2+2=5$）得到 5，或选择第 1、2、3、4 块得到 13 不是倍数，选择第 4 块 8 加第 2 块 2 等于 10（$8+2=10$），这是合法的，且方案有两种：选择第 2 块和第 4 块，或选择第 3 块和第 4 块。

样例2说明： 小珅选择第 1 到第 10 块晶石，总灵力值为 $6 + 12 \times 9 = 114$？不对，总和为 $6 + 12 \times 9 = 114$，114 不是 11 的倍数。实际上，最优方案是选择第 2 到第 10 块晶石（$12 \times 9 = 108$）加上第 1 块 6 等于 114，不对。经过计算，样例2的最大合法总灵力值是 66，可以通过多种组合方式达成，共计 126 种方案。

【数据范围】

对于 100% 的数据： $1 \le n \le 200$ $1 \le F \le 200$ $1 \le a_i \le 100$ $\sum_{i=1}^{n} a_i \le 10000$