小美有一个长度为 的数组，她最多可以进行 次操作，每次操作如下： 1. 选择两个整数 2. 选择两个整数 ，使得 3. 将 替换为 ，将 替换为 她希望最多进行 次操作之后，最后数组中的元素的总和尽可能大。

输入描述:

一行两个整数 ，表示数组的长度和操作的次数。一行 个整数 ，表示数组的元素。

输出描述:

输出一个整数，表示最后数组中的元素的总和的最大值，由于答案可能很大，你只需要输出答案对 取模的结果。