题目描述

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

输入格式

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

输出格式

输出一个整数，表示方案总数，由于这个题答案可能很大，只要输出答案 mod19921107。

1 6

18

数据规模与约定

对于 100% 的数据，1≤p≤10，1≤q≤109，p 和 q 互质