Кажется в этом случае нужно быть аккуратными с четностью палиндромов и пустыми строками.

действительно, можно решать отдельно для четных и нечетных палиндромов

UPD ага, удивительно похоже на задачу с ПТЗ))

Потому что авторское решение, выдающее этот ответ — полный перебор. Будем пытаться перебирать все подходящие неубывающие последовательности сперва длины 2, затем 3 и т.д, пока не сможем получить искомую последовательность.

Перебор будем делать следующим образом. Введем определение "характеристика последовательности" — произведение вида . Очевидно, что при росте a_i характеристика будет уменьшаться и что характеристика всей последовательности, являющейся ответом, равна n. Зафиксируем элемент последовательности (назовем его текущим). Если характеристика последовательности от начала до текущего (не включая его) больше n, то дальше перебирать смысла не имеет (потому что дальше она будет только расти). Иначе же делаем следующее:

1. Установим все элементы последовательности после текущего равным ему (именно это и обеспечивает генерацию неубывающих последовательностей).
2. Посчитаем характеристику всей последовательности.
3. Если она меньше n — перебирать нет смысла, потому что при переборе будут увеличиваться элементы, уменьшая характеристику — выходим.
4. Если она больше n — рекурсивно вызываем перебор, сделав следующий элемент текущим.
5. Если пришли сюда из п.4 и последовательность еще не сгенерирована — увеличиваем текущий элемент на 1 и goto 1.

Ну и, понятно, что как только мы получили последовательность нужной характеристики и нужной длины — выходим. Для оптимизации, если текущий элемент — последний, его можно не перебирать, а получить сразу следующим образом: положим l = П_i = 1^k - 1(a_i + 1), r = П_i = 1^k - 1a_i. Тогда если нужное нам последнее число равно x, то l(x + 1) = n * r * x, откуда x легко находится или определяется, что он не существует.

Уже. Быстро это не напишешь :)

Мы же считаем по модулю 10⁹ + 7. Как учитывать это при делении на k!?

А почему мой пример не подходит?

Обозначать многоугольник принято по порядку обхода вершин. Поэтому условию задачи, в котром говорится о прямоугольнике ABCD, не соответствует ни чертёж к приимеру из условия (ABDC), ни приведённый контпример (ACBD).

Замечу, что в примере к задаче прямоугольник тоже ACDB.

Есть.

Формула где-то ниже, а вот ее док-во: Пусть в каком-то представлении числа n есть хотя бы одна единица (g^0). Тогда этому представлению можно однозначно поставить в соответствие представление для n-1 без этой единицы. Собственно, из любого представления для n-1 можно получить представление для n, просто добавив туда единицу. Очевидно, что все полученные представления различны и для любого представления n с хотя бы одной единицей есть прообраз — представление для n-1. Таким образом, кол-во представлений для n, в которых есть хотя бы одна единица — А(n-1).

Пусть есть представления без единиц. Тогда

1. n mod g=0
2. Их кол-во равно A(n div g) (т.к. легко построить взаимнооднозначное соответствие).

Итого if (n mod g=0) then A(n)=A(n-1)+A(n div g) else A(n)=A(n-1).