Количество дизайнов для стены поистине огромно! Даже по модулю 106 + 3 это всё ещё очень большое число. Учитывая, что недавно у Хайди появились неистощимые поставки кирпичей, количество вариантов для выбора стало совсем уж неприличным. Ей придётся придумать что-нибудь, чтобы урезать количество вариантов.
Хайди сформулировала критерий полезной стены:
- В полезной стене, по крайне мере один фрагмент длиннее w кирпичей. Это должно дать зомби возможность разбить свой лоб о стену. Или,
- в полезной стене, по крайней мере один столбец выше h кирпичей. Это даст возможность наблюдать зомби с удобной и безопасной позиции и обнаружить их заранее.
С помощью этого правила Хайди надеется сильно уменьшим количество подходящих дизайнов. Помогите ей вычислить количество бесполезных стен, которые не удовлетворяют ни одному из условий выше. Другими словами, стена является бесполезной, если каждый её фрагмент имеет ширину не больше чем w и высоту не больше чем h.
Параметр c, суммарная ширина стены, имеет такое же значение, как и в предыдущих версиях данной задачи. Обратите внимание, что количество кирпичей теперь никак не ограничено.
Выведите количество бесполезных стен по модулю 106 + 3.