D2. Стена (средняя)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Выглядит достаточно просто. Однако Хайди всё-таки кодящая корова, а не строящая корова. У неё из головы никак не идёт пункт 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