听说过取数游戏吗？这是一个很简单的游戏，给出N个数D1~Dn。第i次取数的得分是Dx*i（Dx为这次取的数），共取N次，取过的数不能再取；如果这次取得数和上次取的数相等，还能得到额外奖励分数P。取出数字的得分等于各次取数得分的总和。 乌龟希望取数得分最大。

输入的第一行是两个正整数N，P。空格隔开。 接下来N行，每行一个正整数Di。

输出只有一行，由于最高得分可能很大，只要求输出最高得分除以1000的余数。

9 10
1
2
3
4
5
5
6
6
999

186