2044年,Picks建成了人类第一台基于量子理论的银河系信息传递机。
Picks游遍了宇宙,雇用了 $n$ 个外星人来帮他作为信息传递机的中转站。我们将外星人依次编号为 $1$ 到 $n$,其中 $i$ 号外星人有 $a_i$ 根手指。
外星人都是很低级的,于是Picks花费了很大的精力,才教会他们学会扳手指数数。
Picks现在准备传递 $x$ 个脉冲信号给VFleaKing,于是他把信号发给$1$号外星人,然后$1$号外星人把信号发送给$2$号外星人,$2$号外星人把信号发送给$3$号外星人,依次类推,最后$n$号外星人把信号发给VFleaKing。
但是事情没有Picks想象的那么顺利,由于外星人手指个数有限,所以如果 $i$ 号外星人收到了 $t$ 个脉冲信号,他会错误的以为发送过来的是 $t \bmod a_i$ 个脉冲信号,导致只发送了 $t \bmod a_i$ 个脉冲信号出去。
Picks希望他发送出去的脉冲信号数量 $x$ 与VFleaKing收到的脉冲信号数量 $y$ 的差的绝对值尽量小。于是他决定通过重新排列这些外星人的顺序来达到这一目的。请你求出与 $x$ 之差最小的 $y$。除此之外,请求出有多少种排列外星人的方式能达到最优解,你只需要输出方案数对 $998244353$($7 \times 17 \times 2^{23} + 1$,一个质数)取模后的结果。
输入格式
第一行两个正整数$n, x$。
接下来一行有 $n$ 个正整数 $a_i$,表示 $i$ 号外星人的手指数。
输出格式
第一行一个整数表示最优情况下VFleaKing收到的脉冲数量。
第二行一个整数表示达到最优情况的方案数。
样例一
input
2 15 7 10
output
5 1
explanation
共两种可行方案:
- $15 \bmod 7 = 1$,$1 \bmod 10 = 1$
- $15 \bmod 10 = 5$,$5 \bmod 7 = 5$
显然第二种方案更优。
样例二
input
7 33 2 4 6 8 16 16 32
output
1 5040
explanation
每个排列方案都是最优解。
样例三
见样例数据下载
限制与约定
对于每个测试点,答对第一问可获得 40% 的分数,答对第二问可获得 60% 的分数。
请注意你必须输出两个整数否则会判0分。假如你只做了第一问,那么你应该输出你第一问的答案,然后再随便输出一个第二问的答案。
测试点编号 | $n$的规模 | $x$ 和 $a_i$的规模 |
---|---|---|
1 | $n \leq 10$ | $x, a_i \leq 20$ |
2 | $n \leq 50$ | $x, a_i \leq 100$ |
3 | ||
4 | $n \leq 100$ | $x, a_i \leq 500$ |
5 | ||
6 | ||
7 | $n \leq 1000$ | $x, a_i \leq 5000$ |
8 | ||
9 | ||
10 |
时间限制:$1\texttt{s}$
空间限制:$256\texttt{MB}$