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.
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\).
For each test case, output a number in a line, which is the number of schemes modulo \(400823823\).