Ms. Evans has decided to spice up her daily commute by traveling to work on a pogo stick. The sidewalk on her path to work is composed of ~N~ concrete tiles (~1 \leq N \leq 10^5~) numbered from ~1~ to ~N~. Ms. Evans starts at tile ~1~ and wants to end at tile ~N~. Her pogo stick has power ~M~ (~1 \leq M \leq 3~), which means that if she is at tile ~x~, she can travel to any tile ~y~ such that ~|x-y| \leq M~.
Ms. Evans doesn't want to visit any tile more than once, since that would be boring. However, she enjoys jumping so much that she wants to make the maximum number of jumps possible. Please calculate the number of ways she can travel to work while fulfilling the above constraints. Since this number may be very large, you should output it modulo ~10^9+7~.
|Portion of marks||Constraints on ~M~||Constraints on ~N~|
|~5\%~||~M=1~||~1 \leq N \leq 10^5~|
|~10\%~||~M=3~||~1 \leq N \leq 15~|
|~25\%~||~M=2~||~1 \leq N \leq 10^5~|
|~30\%~||~M=3~||~1 \leq N \leq 1000~|
|~30\%~||~M=3~||~1 \leq N \leq 10^5~|
A single line containing ~N~ and ~M~.
A single line containing the answer.