题目描述

求一个数列的所有前缀最大值之和。

即：给出长度为 $n$ 的数列 $a_i$，求出对于所有 $1≤i≤n$，$max(a_1,a_2,...,a_i)$ 的和。

比如，有数列： $666$ $304$ $692$ $188$ $596$，前缀最大值为： $666$ $666$ $692$ $692$ $692$，和为 $3408$。

对于每个位置的前缀最大值解释如下：对于第 $1$ 个数 $666$，只有一个数，一定最大；对于第 $2$ 个数，求出前两个数的最大数，还是 $666$；对于第 $3$ 个数，求出前 $3$ 个数的最大数是 $692……$ 其余位置依次类推，最后求前缀最大值得和。

由于读入较大，数列由随机种子生成。

其中 $a[1]=x$ ， $a[i]=(379 \times a[i-1]+131) \mod 997$ 。（$mod$ 代表求余数）

输入

一行两个正整数 $n,\ x$，分别表示数列的长度和随机种子。($n ≤ 100000$，$x < 997$)

输出

一行一个正整数表示该数列的前缀最大值之和。

样例

5 666

3408

说明

样例解释

数列为 ${666,304,692,188,596}$，前缀最大值为 ${666,666,692,692,692}$，和为 $3408$ 。

来源

动态规划