Вася очень любит изучать разные интересные классы чисел. Сегодня он изучает палиндромные числа.

Вася называет число палиндромным, если оно записывается одинаково слева направо и справа налево. При этом, Вася разрешает приписывать к числу несколько (возможно ни одного) лидирующих нулей. Например, числа 22, 4554, 12321, 5050 являются палиндромными. В частности, к числу 5050 необходимо приписать один ноль, чтобы получить 05050, которое читается одинаково слева направо и справа налево.

В числе прочих, Васю интересуют палиндромные числа, отличающиеся на 2. Для их исследования Вася рассматривает такие \(x\), что \(x-1\) и \(x+1\) являются палиндромными. Такие числа Вася называет междупалиндромными. Вася хочет найти количество междупалиндромных чисел \(x\) от \(L_k\) до \(R_k\) включительно для нескольких отрезков \([L_k, R_k]\).

Помогите Васе в этом нелегком деле!

Недавно на выставку странных устройств привезли новый экспонат. Его суть заключается в том, что он может генерировать случайную перестановку из чисел от \(1\) до \(n\), после чего сканировать ее и выводить на экран \(n - k + 1\) чисел, \(i\)-е из этих чисел обозначает количество инверсий на отрезке с \(i\) по \(i + k - 1\) сгенерированной перестановки.

Напомним, что инверсией в перестановке \(p\) называется всякая пара индексов \(i, j\) такая, что \(1 \le i < j \le n\) и \(p[i] > p[j]\).

У этого экспоната кроме экрана есть две ручки - первая определяет \(n\), то есть длину перестановки, а вторая определяет \(k\). Посетитель Вася повернул ручки и увидел на экране числа. Теперь он хочет понять, какую перестановку сгенерировало это странное устройство. Помогите ему в этом.

Недавно на уроках ИЗО Казимиру рассказали о различных направлениях искусства. Больше всего его впечатлил супрематизм, и он решил нарисовать свою первую картину в этом стиле.

Казимир помнил, что в супрематизме картина состоит из простых фигур, поэтому, сначала он нарисовал прямоугольник \(n \times m\), составленный из разноцветных квадратов \(1 \times 1\). После критического переосмысления своего творения, Казимир пришел к выводу, что получившаяся картина слишком сложна, и не все смогут понять его задумку. Второго холста у него не было, и он решил исправлять эту картину. На достаточно простой картине, по мнению Казимира, должен присутствовать всего один цвет.

Казимир решил исправить картину следующим образом. Он может взять строку своей картины, более половины единичных квадратов в которой покрашено в один и тот же цвет, и перекрасить всю строку в этот цвет. Аналогично он может перекрасить столбец, более половины единичных квадратов в котором покрашено в один цвет.

Помогите Казимиру определить, cможет ли он с помощью этих операций исправить свою картину и сделать ее достаточно простой.

Олег очень любит двоичные последовательности - последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из \(n\) элементов. Для выписанной последовательности Олег посчитал Z-функцию.

Z-функцией последовательности \(s_1, \ldots, s_n\) называется массив \(z[1..n]\), в котором:

• \(z[1] = 0\);
• Если \(i > 1\), то \(z[i]\) равно длине наибольшего общего префикса последовательности \(s\) и суффикса последовательности \(s\), начинающегося с \(i\)-й позиции. Иначе говоря, \(z[i]\) равно максимальному \(k\), такому что \(s_1 = s_i\), \(s_2 = s_{i+1}\), ... , \(s_{k} = s_{i+k-1}\).

Записав в тетради последовательность и ее Z-функцию, Олег лег спать. Пока он спал, его младший брат Егор прокрался в комнату и закрасил фломастером последовательность и некоторые значения Z-функции. Проснувшись, Олег заинтересовался, сколько различных двоичных последовательностей он мог вечером написать в тетради, чтобы незакрашенные значения Z-функции были правильными.

Найдите число искомых последовательностей и выведите его по модулю \(10^9 + 7\). Заметьте, что Олег мог и ошибиться при вычислении Z-функции, в этом случае ни одна последовательность не подходит и ответ равен 0.

3
0 0 1

2

4
0 0 1 0

0

3
0 3 -1

0

3
-1 -1 -1

8