ИТ-кампус Неймарк проводит множество соревнований! По итогам соревнования победители получают ценные призы, причем чем выше место, тем лучше приз (или, по крайней мере, не хуже). Иногда на соревновании дают дипломы первой степени («победители») и дипломы второй степени («призёры»). Иногда дают дипломы первой, второй, третьей степени.

Возможно, в недалеком будущем на соревнованиях будут вручать $$$m$$$ различных видов дипломов — дипломы степени $$$1$$$, дипломы степени $$$2$$$, ..., дипломы степени $$$m$$$. Чем лучше диплом (то есть, чем меньше его номер), тем более значимо достижение участника. Поэтому логично предположить, что дипломов степени $$$i$$$ будет вручено меньше, чем дипломов степени $$$j$$$ при $$$i \lt j$$$. Далее для простоты будем полагать, что на соревновании вручается ровно $$$i$$$ дипломов степени $$$i$$$ для всех $$$i$$$ от $$$1$$$ до $$$m$$$.

Сотрудники кампуса готовы к такому количеству дипломов! Более того, они запасли множество ценных призов. Всего было запасено $$$n$$$ видов призов, причем по аналогии с дипломами приз типа $$$i$$$ считается лучше, чем приз типа $$$j$$$, если $$$i \lt j$$$. Более ценные призы являются более дорогими, поэтому их было запасено меньше. А именно: было выбрано натуральное число $$$a$$$ и призов типа $$$i$$$ было заготовлено ровно $$$(i + a - 1)$$$ штук.

Наконец, настало время раздавать призы победителям! При раздаче призов должны выполняться следующие естественные условия:

• все участники, получившие одинаковые дипломы, должны получить одинаковые призы (допускается, что участники с разными дипломами тоже получат одинаковые призы);
• участники с дипломами степени $$$i$$$ должны получить призы не хуже, чем участники с дипломами степени $$$j$$$ для всех пар $$$1 \leq i \lt j \leq m$$$;
• каждый участник должен получить ровно один приз;
• призов типа $$$i$$$ должно быть использовано не более, чем имеется в наличии — $$$(i + a - 1)$$$ (допускается, что призы некоторых типов будут в избытке или вообще не будут использованы).

От вас требуется найти количество различных способов раздать призы участникам. Два способа считаются различными, если хотя бы один участник получил приз другого типа. Поскольку ответ может быть очень большим, нужно вывести лишь его остаток от деления на $$$10^9+7$$$.