Piggy Bank :
Difficulty Level : Hard
Submissions : 135
Asked In :
Marks :10
: 0 | : 1
Daniel has $$$2$$$ piggy banks. A bigger one and a smaller one. He has divided the bigger piggy bank in $$$n$$$ slots and smaller piggy bank in $$$m$$$ slots, $$$n > m$$$. He has some money deposited in both of them. He chooses $$$m$$$ slots from the bigger piggy bank and transfers their money to $$$m$$$ slots of smaller piggy bank in respective order. He wants that the amount in slot $$$i+1$$$ should always be greater than or equal to that in the slot $$$i$$$, of the smaller piggy bank, after the transfer from the bigger piggy bank. You have to help Daniel to count the number of ways he can transfer the money. Since, the number of ways can be large output it modulo $$$10^9+7$$$.
The first line contains $$$2$$$ integers $$$n,m(1 \leq m < n \leq 1000)$$$.
The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(1 \leq a_i \leq 10^9)$$$, the amounts in the $$$n$$$ slots of the bigger piggy bank.
The next line contains $$$m$$$ integers $$$b_1,b_2,...,b_m(1 \leq b_i \leq 10^9)$$$, the amounts in the $$$m$$$ slots of the bigger piggy bank.
Output a single integer - the number of ways Daniel can transfer the money modulo $$$10^9+7$$$.
5 3 9 7 10 3 1 6 7 10
0
