F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister 捐赠本站
Notice:开心刷题:)
Problem 2126. -- 排斥反应 -- 衡阳八中OJ离线版-2014-11-04

2126: 排斥反应

Time Limit: 40 Sec  Memory Limit: 259 MB
Submit: 201  Solved: 97
[Submit][Status]

Description

在一个圆上均匀分布p*q个点{A1,A2,A3…Ap*q},Ai与Aj的距离为min{abs(i-j),p*q-abs(i-j)},在上面选任意个点(可以选0个),如果选择的点中存在两个点距离为p或q,就会发生排斥反应,求不发生排斥反应的方案总数。

Input

输入的第一行包含两个整数,分别表示p和q

Output

输出一个整数,表示方案总数,由于这个题答案可能很大,只要输出答案mod 19921107

Sample Input

1 6

Sample Output

18
【数据说明】
对于100%的数据,p<=10,q<=10^9,p和q互质

HINT

Source

[Submit][Status]

HOME Back