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