{"problem":{"name":"Product Modulo","description":{"content":"Let’s take a prime $P = 200\\,003$. You are given $N$ integers $A_1, A_2, \\ldots, A_N$. Find the sum of $((A_i \\cdot A_j) \\bmod P)$ over all $N \\cdot (N-1) / 2$ unordered pairs of elements ($i < j$). P","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc047_c"},"statements":[{"statement_type":"Markdown","content":"Let’s take a prime $P = 200\\,003$. You are given $N$ integers $A_1, A_2, \\ldots, A_N$. Find the sum of $((A_i \\cdot A_j) \\bmod P)$ over all $N \\cdot (N-1) / 2$ unordered pairs of elements ($i < j$).\nPlease note that the sum isn't computed modulo $P$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 200\\,000$\n*   $0 \\leq A_i < P = 200\\,003$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format.\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc047_c","tags":[],"sample_group":[["4\n2019 0 2020 200002","474287\n\nThe non-zero products are:\n\n*   $2019 \\cdot 2020 \\bmod P = 78320$\n*   $2019 \\cdot 200002 \\bmod P = 197984$\n*   $2020 \\cdot 200002 \\bmod P = 197983$\n\nSo the answer is $0 + 78320 + 197984 + 0 + 0 + 197983 = 474287$."],["5\n1 1 2 2 100000","600013"]],"created_at":"2026-03-03 11:01:14"}}