Корова Хайди в шоке: в северной стене появились трещины? Зомби собираются и готовятся к нападению? Этого не должно произойти! Она быстро просмотрела свою методичку по безумным постройкам и нашла подходящую главу:
Как построить стену:
- Возьмите набор кирпичей.
- Выберите один из возможных дизайнов стены. Вычисление количества различных дизайнов оставлено читателю в качестве упражнения.
- Положите кирпичи друг на друга, чтобы образовать стену соответствующего дизайна.
Выглядит достаточно просто. Однако Хайди всё-таки кодящая корова, а не строящая корова. У неё из головы никак не идёт пункт 2b. Несмотря на серьёзную опасность и толпы зомби на подходе, она всё-таки хочет посчитать количество различных стен, которые она может построить с помощью n кирпичей.
Стеной называется набор фрагментов стены, определяемый аналогично предыдущей задаче. Сколько различных стен может быть построено, состоящих из не менее чем 1 и не более чем n кирпичей? Две стены считаются различными, если существует столбец i и ряд j, такие что у одной стены есть кирпич в этом месте, а у другой нет.
Помимо n вам также будет дано значение параметра c, определяющего ширину стены (аналогично лёгкой версии задачи). Выведите количество различных стен по модулю 106 + 3.