Корова Хайди в шоке: в северной стене появились трещины? Зомби собираются и готовятся к нападению? Этого не должно произойти! Она быстро просмотрела свою методичку по безумным постройкам и нашла подходящую главу:

Как построить стену:

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

Выглядит достаточно просто. Однако Хайди всё-таки кодящая корова, а не строящая корова. У неё из головы никак не идёт пункт 2b. Несмотря на серьёзную опасность и толпы зомби на подходе, она всё-таки хочет посчитать количество различных стен, которые она может построить с помощью n кирпичей.

Стеной называется набор фрагментов стены, определяемый аналогично предыдущей задаче. Сколько различных стен может быть построено, состоящих из не менее чем 1 и не более чем n кирпичей? Две стены считаются различными, если существует столбец i и ряд j, такие что у одной стены есть кирпич в этом месте, а у другой нет.

Помимо n вам также будет дано значение параметра c, определяющего ширину стены (аналогично лёгкой версии задачи). Выведите количество различных стен по модулю 10⁶ + 3.