#agc054f. [agc054_f]Decrement
[agc054_f]Decrement
Problem Statement
Given is a sequence of positive integers and a sequence of positive integers. You can do the following operation any number of times.
- Choose integers and () and decrease each of the following values by : . Here, there should not be any negative value after this operation.
Let be the maximum number of operations that can be done. Find the number, modulo , of sequences that can be after operations.
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1
Sample Output 1
We have . After two operations, will be one of the following three sequences.
- : we end up with this after operations with and .
- : we end up with this after operations with and .
- : we end up with this after operations with and .
Sample Input 2
Sample Output 2
Note that we do not distinguish two scenarios with different contents of if the contents of are the same.