28727번 - Ограбление банка 다국어

문제

Джокер грабит банк. Всё, что нужно, чтобы обогатиться --- вскрыть кодовый замок от хранилища с деньгами. Код от замка представляет собой строку длины $n$ из латинских букв. Также Джокер стащил у нерадивого охранника записку, на которой указана подсказка к коду. Сопоставим символам от <<a>> до <<z>> числа от 0ドル$ до 25ドル$. В подсказке указаны $n$ целых чисел $a_i$: $a_1$ равно числу, соответствующему первому символу кода, а для всех 2ドル \le i \le n$ $a_i$ равно модулю разности чисел, соответствующих символам на позициях $i - 1$ и $i$.

В это время Доктор Стрэндж, путешествуя между мирами, попал не в ту вселенную и угодил прямиком в руки Джокера. И теперь, используя Глаз Агамотто, Джокер планирует перебрать все 14ドル,000円,625円$ вариантов комбинаций кода и найти единственную подходящую. На самом деле возможных комбинаций может оказаться и не 14ドル,000円,625円$ --- Джокер сказал это число наугад. Поэтому он решил выяснить реальное количество различных кодов, которые удовлетворяют данным из подсказки. Помогите ему вычислить это число. Поскольку Джокер сумасшедший, вместо самого числа он попросил вас посчитать остаток от деления этого числа на 1ドル,000円,000円,007円$.

입력

В первой строке дано одно число целое число $n$ --- длина кода (1ドル \le n \le 10^6$). Во второй строке дано $n$ целых чисел $a_i$ (0ドル \le a_i \le 25$).

출력

В единственной строке выведите одно число --- количество различных комбинаций, которые соответствуют информации из подсказки, по модулю 10ドル^9 + 7$.

제한

노트

В первом тесте единственным подходящим кодом является <<e>>.

Во втором тесте подсказке удовлетворяют следующие коды: <<mie>>, <<mim>>, <<mqm>>, <<mqu>>.