Tổng Cặp Tích

View as PDF




Time limit:
Pypy 3 2.5s
Python 3 2.5s
Memory limit:
Pypy 3 500M
Python 3 500M

Author:
Problem type
Points: 1000 (p) Time limit: 0.5s Memory limit: 256M Input: stdin Output: stdout

Cho mảng \(A\) gồm \(N\) số nguyên dương.

Yêu cầu: Hãy in ra tổng tất cả các cặp \((A_i \times A_j)\) với mọi cặp \((i,j)\) thỏa mãn \(1\le i<j\le N\) , chia lấy dư cho \(({10}^9+7)\). Hay nói cách khác: tổng tất cả các cặp tích của mảng.

Input

  • Dòng đầu tiên nhập số nguyên dương \(N\) \((2\le N\le2\times{10}^5)\).
  • Dòng còn lại nhập \(N\) số tiếp theo – là các phần tử của mảng \((1\le A_i\le{10}^9)\).

Output

  • In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài sau khi chia lấy dư cho \(({10}^9+7)\).

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): Có \(N\le{10}^3\).
  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
3
1 2 3
Output
11
Note

Ta có \((1\times2)+(1\times3)+(2\times3)=11\).


Comments


  • 0
    nghia250610    2:46 p.m. 24 jun, 2024

    mang cong don


    • 4
      penistone    10:06 p.m. 24 dec, 2023 edit 2
      Hint

      Tổng tích lũy + mod. Lưu ý rằng \(A_i\) <=\(10^9\) nên ta phải mod liên tục
      Code C++ tại đây