Каті подарували валентинку, на якій було написано \(n\) чисел \(a_i\). Зрозуміло, Катя відразу ж вирішила порахувати \(\displaystyle \sum_{i <j} a_i \cdot a_j\). Оскільки Катя хотіла, щоб відповідь вийшла маленькою, але не дуже, Катя вирішила брати всі добутки за модулем \(P = 200'003\), а суму за модулем \textbf{не брати}.

Таким чином, від вас потрібно порахувати \(\displaystyle \sum_{i < j} ((a_i \cdot a_j) \pmod{P})\). Успіхів!

Формат вхідних даних

У першому рядку вводиться число \(n\) (\(2 \le n \le 200'000\))~--- кількість чисел на валентинці.

У наступному рядку через пробіл вводиться \(n\) чисел \(a_i\) (\(0 \le a_i \le P-1\))~--- послідовність чисел з валентинки.

Формат вихідних даних

Виведіть одне число -\(\displaystyle \sum_{i < j} ((a_i \cdot a_j) \pmod{P})\).

Приклад вхідних даних

4
2019 0 2020 200002

Приклад вихідних даних

474287

Приклад вхідних даних

5
1 1 2 2 100000

Приклад вихідних даних

600013