Cho mảng \(A\) gồm \(n\) phần tử nguyên. Tìm một tập con sao cho tổng của nó chia lấy dư cho \(10^9\) là lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai gồm nsố nguyên \(A_i\).

Output

• In ra giá trị lớn nhất

Điều kiện

• \(1 \le n \le 40\)
• \(|A_i|\le 10^{9}\)

Sample Input 1

3
1000000000 1000000000 6

Sample Output 1

6