406769: GYM102536 H Maggie and Dana's Mass Supper

Two best friends Maggie and Dana attend church mass at their hometown every Monday. They usually wake up at 10:00 am, attend mass at 11:23 am (the priest is really strict with regards to time), and finish at 3:00 pm. After that, most of their free time is spent reading books, finding stories, and keeping up to date with the news.

Today however, November 23 is a special day for both of them, as there's a supper happening this evening in their honor. Their other best friend Esmael has invited 58 guests in to his house to celebrate! Obviously, Maggie and Dana are very excited to attend the supper.

There's a slight problem though: the supper is located at the other end of region, so they have to walk across to get there! The region can be represented as an $$$\ell \times w$$$ rectangular grid, where the upper left corner is the church where Maggie and Dana will be coming from, and the bottom right corner being the supper location. Maggie and Dana can only move either directly downwards or rightwards (towards the destination).

Local bullies Andall and Zaldie hear about this, so they decide to make it hard for Maggie and Dana to get there. They decide to block specific parts of the region to limit Maggie and Dana's movement. For example, for $$$\ell = 7$$$ and $$$w = 5$$$:

...####
#...###
##...##
###...#
####...

Here, # represents a cell that is blocked, and . represents a cell that is not blocked.

They only leave a cascading path $$$\ell - w + 1$$$ wide for Maggie and Dana to get through! Maggie and Dana note that this is only possible due to their home province's unique geography, where its length is larger than its width ($$$\ell > w$$$). The cascading path shifts to the right by $$$1$$$ step for each row down in the region, where it ends at the bottom-right corner.

Now, Maggie and Dana want to know how many ways they can get to Esmael's supper, given that they are being blocked by Andall and Zaldie. Help them find that out!

The input consists of a single line containing two space-separated integers $$$\ell$$$ and $$$w$$$, the length and width of the region Maggie and Dana live in.

Constraints

• $$$1 \le w \le 5\cdot 10^5$$$
• $$$1 \le \ell \le 5\cdot 10^6$$$
• $$$w < \ell$$$
• It is guaranteed that there is at least one path, i.e., the grid is not degenerate.

Output a single line containing a single integer denoting the number of paths Maggie and Dana can take from the upper left corner (the church) to the bottom right corner (Esmael's supper), assuming Andall and Zaldie blocked the region in the way described above. Since the answer may be very large, only output it modulo $$$104857601$$$.

7 5

16