Le Juste Étal – Qualification 2025

Niveau 3 ⋅ Validation weight: 15%

Énoncé

Joseph Nageant est enfin à l'intérieur de la ville sous-marine secrète.

En avançant, il s'aperçoit qu'un événement a lieu : c'est le marché !

Joseph tente de côtoyer un marchand afin d'obtenir de précieuses informations. Pour cela, il aide le marchand à préparer ses boîtes contenant des fruits et légumes.

Les boîtes sont arrangées sur un étal, et sont représentées par un tableau de $N$ nombres entiers, le nombre de fruits ou légumes dans chaque boîte.

Une série de boîtes décrit une sous-séquence contigue de l'étal. Une série peut être représentée par deux indices $0 \leq i < j \leq N$, représentant l'indice de début (inclus) et l'indice de fin (exclu) de la série. Par exemple, si les boîtes sont représentées par la suite $B = [1, 3, 2, 1, 3]$, alors la paire $(0, 2)$ représente la série $[1, 3]$. Notez que la paire $(3, 5)$ représente aussi la série $[1, 3]$, et les deux séries sont considérées comme distinctes.

Une série est dite juste si le nombre total de fruits et légumes présents dans la série est un multiple de la valeur du marché du jour.

Afin de maximiser les ventes, le marchand veut savoir le nombre de séries justes dans son étal. Il vous donne des informations sur les boîtes ainsi que la valeur du marché du jour.

Comme la réponse peut être grande, affichez la réponse modulo $1\,000\,000\,007$.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de boites.
  • Sur la ligne suivante, un entier : valeur, la valeur du marché du jour.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : boites, le contenu de chaque boite.

Sortie

Afficher, sur une ligne, un unique entier : le nombre de séries justes modulo $1\,000\,000\,007$.

Contraintes

  • $1 \le N \le 100$
  • $1 \le valeur \le 1\,000\,000\,000$
  • $0 \le \mathtt{boites}_i \le 1\,000\,000\,006$

Contraintes de performance

  • $1 \le N \le 1\,000\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
4
0 1 3 1 3 2
Exemple de sortie
7
Commentaire

Ici, il y a 6 boites 0 1 3 1 3 2 et la valeur du marché du jour est $4$.

Voici les séries dont la somme est un multiple de $4$ :

   i       j       série       somme   
0 1 (0) 0
0 3 (0, 1, 3) 4
0 5 (0, 1, 3, 1, 3) 8
1 3 (1, 3) 4
1 5 (1, 3, 1, 3) 8
2 4 (3, 1) 4
3 5 (1, 3) 4

Il n'y en a pas d'autre, on affichera donc 7.

Exemple d'entrée
4
4
0 0 0 0
Exemple de sortie
10
Commentaire

Ici, il y a 4 boites vides.

Il est possible de former 10 séries, qui auront tous la somme de 0 (qui est un multiple de 4 car $4 \times 0 = 0$).

On doit donc afficher $10$.

Exemple d'entrée
9
11
1 1 1 1 1 1 1 1 1
Exemple de sortie
0