Problem R: Chanming Choosing Treasures

Problem R: Chanming Choosing Treasures

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 60  Solved: 12
[Submit][Status][Web Board]

Description

Chanming has finally reached the City N. Here, he found \(n\) kinds of treasures, and there are \(a[i]\) treasures of the \(i\)-th kind.

Chanming has three best friends. He is going to bring three treasures back and shows off to his friends. However, he can bring at most one treasure of each kind.

Chanming wants to know how many different schemes to bring treasures there are.

Input

There are multiple test cases, please process until the end of file (EOF).

For each test case, the first line contains an integer \(n (3\leq n\leq 3000)\), representing the number of kinds of treasures. The second line contains \(n\) integers, which is the array \(a[]\), and \(a[i]\leq 10000\).

Output

For each test case, output a number in a line, which is the number of schemes modulo \(400823823\).

Sample Input

3
1 2 3

Sample Output

6

HINT

[Submit][Status]