Это hard версия задачи. Отличие между версиями заключается в том, что в этой версии не обязательно \(a_i = 0\). Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Есть \(n\)-этажный дом, этажи пронумерованы от \(1\) до \(n\) снизу вверх. На каждом этаже живёт ровно один человек.
У всех жителей дома сегодня есть важная цель: запустить всем домом суммарно хотя бы \(c\) бумажных самолётиков. Жители будут запускать самолётики поочерёдно. Когда человек с \(i\)-го этажа запускает самолётик, это видят все жители на этажах от \(1\) до \(i\), пока самолёт опускается на землю. Если с точки зрения жителя с \(i\)-го этажа уже было запущено хотя бы \(c\) самолётиков, сам он больше не будет запускать самолётики. Также известно, что в конце дня, с точки зрения каждого из жителей дома, было запущено хотя бы \(c\) самолётиков, а всего было кинуто \(m\) самолётиков.
Вы внимательно следили за данным флешмобом, и для каждого самолётика записывали, житель какого из этажей его кинул. Но, к сожалению, информация о том, кто именно кидал некоторые самолётики, была утеряна. Найдите количество способов заполнить пропуски, чтобы информация могла быть достоверной. Так как ответ может быть достаточно большим, выведите его по модулю \(10^9 + 7\).
Также возможна ситуация, что вы ошиблись в своих записях, и не существует ни одного возможного способа восстановить пропуски. В таком случае ответ считается равным \(0\).
Выходные данные
Для каждого набора входных данных выведите количество способов заполнить пропуски числами от \(1\) до \(n\), чтобы хронология запуска самолётиков могла быть достоверной, по модулю \(10^9 + 7\).
Примечание
В первом тестовом примере все шесть возможных способов заполнить пропуски таковы:
- \([1, 1, 3, 3]\)
- \([1, 2, 3, 3]\)
- \([1, 3, 2, 3]\)
- \([2, 1, 3, 3]\)
- \([2, 2, 3, 3]\)
- \([3, 1, 2, 3]\)
Обратите внимание, что массив \([2, 3, 1, 3]\) не является валидным способом заполнить пропуски, так как третий самолётик не мог быть запущен человеком с \(1\) этажа, так как с его точки зрения уже было запущено \(c = 2\) самолётика.
Также массив \([1, 1, 2, 3]\) не является валидным способом заполнить пропуски, так как с точки зрения человека с \(3\) этажа всего был запущен только \(1\) самолётик, а \(c = 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
3 2 4
0 0 0 0
5 5 7
0 0 0 0 0 0 0
6 1 3
2 0 0
2 3 5
0 0 1 0 2
3 3 4
3 3 3 0
2 1 2
0 1
2 1 2
0 2
5 3 12
0 0 1 0 2 4 0 0 0 5 0 5
|
6
190
3
2
0
0
1
14
|