#arc162f. [arc162_f]Montage
[arc162_f]Montage
Problem Statement
You are given positive integers and . Among the matrices with rows and columns where each element is or , find the number, modulo , of ones that satisfy the following condition:
- $A_{a, b} \\times A_{c, d} \\leq A_{a, d} \\times A_{c, b}$ for every quadruple of integers such that and .
Constraints
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the answer in a single line.
Sample Input 1
2 2
Sample Output 1
13
The condition is $A_{1,1} \\times A_{2,2} \\leq A_{1,2} \\times A_{2,1}$. All matrices other than $\\begin{pmatrix} 1 & 0 \\\\ 0 & 1 \\end{pmatrix}, \\begin{pmatrix} 1 & 1 \\\\ 0 & 1 \\end{pmatrix}, \\begin{pmatrix} 1 & 0 \\\\ 1 & 1 \\end{pmatrix}$ satisfy the condition.
Sample Input 2
1 30
Sample Output 2
75497471
All matrices satisfy the condition, so print modulo , that is, .
Sample Input 3
400 400
Sample Output 3
412670892