La Partie de Mahjong – Qualification 2026

Niveau 4 ⋅ Validation weight: 15%

Énoncé

Joseph Marchand se rend maintenant dans un bâtiment abandonné, en espérant pouvoir trouver des informations utiles au retour des humains sur Terre.

À l'entrée du bâtiment, Joseph rencontre Rob-Espierre accompagné d'un groupe de robots indépendantistes. Ces robots sont contre le retour des humains, car ils pensent que ces derniers possèdent une intelligence inférieure. Pour leur prouver le contraire, Joseph leur propose un défi : compter le nombre de mains dans un jeu de Mahjong.

Le jeu contient des tuiles portant un numéro entre $1$ et $N$. La tuile portant le numéro $i$ existe en $a_i$ exemplaires. L'objectif est de répartir les tuiles en une main vide ou composée d'un ou plusieurs éléments. Une main est considérée comme complète si chaque tuile existante dans le jeu a été répartie dans exactement un élément. Une tuile ne peut être utilisée pour former qu'un seul élément.

Un élément peut être formé de deux façons :

  • On peut former un élément avec trois exemplaires de tuiles portant le même numéro
  • On peut former un élément avec trois exemplaires de tuiles portant des numéros consécutifs, c'est-à-dire que pour $i$ choisi dans $[1, N-2]$, on peut former un élément avec les tuiles $i, i+1, i+2$

Joseph doit compter combien de mains complètes différentes il peut créer dans un jeu de Mahjong. Deux mains complètes A et B sont considérées différentes si un élément n'est pas présent le même nombre de fois dans A que dans B. Aide Joseph à trouver la réponse à sa question. Comme la réponse peut être très grande, on demande son reste par la division avec $10^9 + 7$.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de numéros de tuiles disponibles.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : $a_i$, le nombre d'exemplaires de la tuile portant le numéro $i$.

Sortie

Afficher en sortie le reste de la division par $10^9 + 7$ du nombre de mains complètes différentes que Joseph Marchand peut former avec les tuiles disponibles.

Contraintes

  • $1 \le N \le 30$
  • $0 \le a_i \le 30$

Contraintes de performance

  • $1 \le N \le 200$
  • $0 \le a_i \le 200$

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
4
3 3 3 3
Exemple de sortie
3
Commentaire

Il existe trois manières de former une main complète :

  • Trois fois l'élément composé des tuiles 1, 2, 3 et une fois l'élément composé des tuiles 4, 4, 4
  • Trois fois l'élément composé des tuiles 2, 3, 4 et une fois l'élément composé des tuiles 1, 1, 1
  • Les quatre éléments composés de trois fois les mêmes tuiles entre 1 et 4

Le reste de la division euclidienne de 3 par $10^9+7$ est 3 donc la réponse attendue est 3.

Exemple d'entrée
5
1 3 1 3 1
Exemple de sortie
0
Commentaire

Il est possible de prouver que les tuiles ne peuvent pas être regroupées en éléments pour former une main complète.

Exemple d'entrée
10
11 11 13 14 18 18 17 20 12 13
Exemple de sortie
5779