一个长度为 $n$ 的数组 $a$，我们可以把它分成任意组，每一组是一段连续的区间。比如数组 $1,2,3,4,5$ 可以分成 $(1,2),(3,4,5)$两个组。

每个分组都有一个权值，这个权值就是分组里面每个数的乘积对 $1000$ 取模的结果。

对于数组 $a$ 的一个分组方案，总权值就是每个分组的权值和。

那么对于数组 $a$，分组以后最大的权值和是多少？

输入格式

输入第一张一个整数 $n(1≤n≤1000)$。

接下来一行 $n$ 个整数，表示数组 $a$，数组中每个元素都小于等于 $100$。

输出格式

数组最大的分组权值和。

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 split.in，输出文件为 split.out

样例输入

7
52 26 1 36 72 48 43

样例输出

1596