Given an array $A$ of $n$ integers. Find a subset of $A$ so that its sum modulo $10^9$ is maximum.
In other words, find $k \le n$ indices $i_1, i_2,...,i_k$ so that:
$$A_{i_1} + A_{i_2} + ... + A_{i_k} \mod 10^9$$
is maximum.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $A_i$.
### Output
- Prin the maximum value of $A_{i_1} + A_{i_2} + ... + A_{i_k} \mod 10^9$.
### Constraints
- $1 \le n \le 40$.
- $1 \le A_i \le 10^9$.
### Example
Input:
```
3
1000000000 1000000000 6
```
Output:
```
6
```