#arc116c. [arc116_c]Multiple Sequences
[arc116_c]Multiple Sequences
Problem Statement
Given are integers and . How many sequences of integers satisfy the following conditions?
- $1 \\leq A_i \\leq M \\left(i = 1, 2, \\ldots, N\\right)$
- is a multiple of .
Since the answer can be enormous, report it modulo .
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
3 4
Sample Output 1
13
Some of the sequences satisfying the conditions follow:
Sample Input 2
20 30
Sample Output 2
71166
Sample Input 3
200000 200000
Sample Output 3
835917264