Rezolvare PBinfo #3752

Se consideră numerele naturale nenule N și D urmate de o secvență S de N numere naturale nenule ordonate crescător, indexate de la 1 la N.

Cerința

Să se determine numărul de cvintete de indici (i1, i2, i3, i4, i5) ce verifică relațiile:

• a • b • c = D
• a • x2 + b • y2 = c2
• a < b < c
• x ≠ y

unde am notat cu a = S[i1], b = S[i2], c = S[i3], x = S[i4], y = S[i5]. Rezultatul se va afișa modulo 1.000.000.007.

Date de intrare

Fișierul de intrare cvintete.in conține pe prima linie două numere naturale nenule N și D cu semnificația
din enunț. Pe următoarea linie se vor afla N numere naturale nenule ordonate crescător.

Date de ieșire

Fișierul de ieșire cvintete.out va conține un singur număr natural care reprezintă rezultatul cerinței, modulo 1.000.000.007.

Subtask-uri

• Subtask 1 (16 puncte): 1 ≤ N ≤ 20, 1 ≤ S[i] ≤ 20, 1 ≤ D ≤ 250
• Subtask 2 (12 puncte): 1 ≤ N ≤ 1000, 1 ≤ S[i] ≤ 1000, 1 ≤ D ≤ 100.000
• Subtask 3 (25 puncte): 1 ≤ N ≤ 5000, 1 ≤ D ≤ 10.000.000, S[i]=i, pentru orice 1 ≤ i ≤ N
• Subtask 4 (28 puncte): 1 ≤ N ≤ 10.000, 1 ≤ S[i] ≤ 5000, 1 ≤ D ≤ 10.000.000
• Subtask 5 (19 puncte): 1 ≤ N ≤ 100.000, 1 ≤ S[i] ≤ 20.000, 1 ≤ D ≤ 1.000.000.000
• Pentru toate subtask-urile, se respectă relația S[i] ≤ S[i + 1], oricare ar fi 1 ≤ i ≤ N - 1.

Exemplul 1:

cvintete.in

4 6
1 2 3 3

cvintete.out

2

Explicație

Cvintetele care respectă cerința sunt: (1, 2, 3, 1, 2), (1, 2, 4, 1, 2).

Exemplul 2:

cvintete.in

10 60
1 2 3 4 4 5 6 8 10 12

cvintete.out

4

Explicație

Cvintetele care respectă cerința sunt: (1, 6, 10, 8, 4), (1, 6, 10, 8, 5), (1, 7, 9, 2, 4), (1, 7, 9, 2, 5)