Description

Given two matrices A and B with the same size n × n, and parameters a₁, a₂, b₁, b₂, the two matrices are defined as:

• A(i,j) = i × a₁ + j × a₂
• B(i,j) = i × b₁ + j × b₂

where i, j are 0, 1, 2, ⋯, n − 1.

Calculate the sum of all elements of C = AB.

Input

No more than 10 test cases. For each case, n a₁ a₂ b₁ b₂ are given.

• 1 ≤ n ≤ 1000
• 1 ≤ a₁, a₂, b₁, b₂ ≤ 10⁵

Output

The sum mod by 10⁹ + 7.

2 1 1 1 1
4 1 2 3 4

10
3504