1394: 简单游戏
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：313
Solved：23
Description
某天，emaster发现了一个沙雕小游戏
在这个游戏中，玩家扮演小人奔跑，每隔一段距离将会出现两扇带有算式的门，玩家可以选择一扇通过，同时自身的数字也会与门上的算式进行运算，游戏最终得分为到达终点时自身的数字
emaster认为这个游戏对于大学生还是太过于困难了，他决定使用科技。
现在，游戏中共$n$扇门，玩家必须依顺序通过所有的门。第${i}$扇门上会标有一个正整数$a_{i}$。玩家的初始得分为$sum(sum=1)$，emaster拥有科技，每次经过第${i}$扇门时，玩家须从以下操作选择一项执行之。
1.sum+=$a_{i}$(sum加$a_{i}$）
2.sum*=$a_{i}$(sum乘$a_{i}$）
emaster试了试修改后的游戏，觉得这个游戏对于acmer还是太简单了，他决定让你选择其中的$m$扇门，经过这些门时不再执行上述操作，
改为执行sum%=$a_{i}$(sum对$a_{i}$取模）
你的目标是让经过$n$扇门后的得分最大
快来秒了这个简单的游戏吧~
注意：emaster拥有科技，当玩家得分sum=0时游戏不会结束。初始分数固定为1。由于答案可能非常大，请输出其对 998244353 取模后的结果
在这个游戏中，玩家扮演小人奔跑，每隔一段距离将会出现两扇带有算式的门，玩家可以选择一扇通过，同时自身的数字也会与门上的算式进行运算，游戏最终得分为到达终点时自身的数字
emaster认为这个游戏对于大学生还是太过于困难了，他决定使用科技。
现在，游戏中共$n$扇门，玩家必须依顺序通过所有的门。第${i}$扇门上会标有一个正整数$a_{i}$。玩家的初始得分为$sum(sum=1)$，emaster拥有科技，每次经过第${i}$扇门时，玩家须从以下操作选择一项执行之。
1.sum+=$a_{i}$(sum加$a_{i}$）
2.sum*=$a_{i}$(sum乘$a_{i}$）
emaster试了试修改后的游戏，觉得这个游戏对于acmer还是太简单了，他决定让你选择其中的$m$扇门，经过这些门时不再执行上述操作，
改为执行sum%=$a_{i}$(sum对$a_{i}$取模）
你的目标是让经过$n$扇门后的得分最大
快来秒了这个简单的游戏吧~
注意：emaster拥有科技，当玩家得分sum=0时游戏不会结束。初始分数固定为1。由于答案可能非常大，请输出其对 998244353 取模后的结果
Input
第一行两个整数$n$，$m$;代表门的总数和你需要选择的门的数量
第二行$n$个整数$a_{1}$，$a_{2}$，$a_{3}$， ..., $a_{n}$ 代表每扇门上的数字
数据范围：
$1 \le n \le 10^5$
$0 \le m \le n$
门上的数字满足：$1 \le a_{i} \le 10^9$
第二行$n$个整数$a_{1}$，$a_{2}$，$a_{3}$， ..., $a_{n}$ 代表每扇门上的数字
数据范围：
$1 \le n \le 10^5$
$0 \le m \le n$
门上的数字满足：$1 \le a_{i} \le 10^9$
Output
一个整数，最大得分对 998244353 取模后的结果
Sample Input Copy
6 1
1 1 4 5 1 4
Sample Output Copy
104HINT
对于样例，我们需要选择在其中一扇门进行取模操作。
第一扇门时选择取模sum%=$a_{1}$,通过后sum=0;
到第二扇门时选择sum+=$a_{2}$,通过后sum=1;
到第三扇门时选择sum+=$a_{3}$,通过后sum=5;
到第四扇门时选择sum*=$a_{4}$,通过后sum=25;
到第五扇门时选择sum+=$a_{5}$,通过后sum=26;
到第六扇门时选择sum*=$a_{6}$,通过后sum=104;
104%998244353=104;故输出104.
可以发现没有比这样做更优的决策
ps.请使用较大的数据类型
第一扇门时选择取模sum%=$a_{1}$,通过后sum=0;
到第二扇门时选择sum+=$a_{2}$,通过后sum=1;
到第三扇门时选择sum+=$a_{3}$,通过后sum=5;
到第四扇门时选择sum*=$a_{4}$,通过后sum=25;
到第五扇门时选择sum+=$a_{5}$,通过后sum=26;
到第六扇门时选择sum*=$a_{6}$,通过后sum=104;
104%998244353=104;故输出104.
可以发现没有比这样做更优的决策
ps.请使用较大的数据类型