题目描述

在一个圆上均匀分布 $p\times q$ 个点 ${A_1,A_2,A_3\dots A_{p\times q}}$，$A_i$ 与 $A_j$ 的距离为 $\min\{\left|(i-j)\right|，p\times q - \left|(i-j)\right|\}$，在上面选任意个点（可以选 $0$ 个），如果选择的点中存在两个点距离为 $p$ 或 $q$，就会发生排斥反应，求不发生排斥反应的方案总数。

输入格式

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

输出格式

输出一个整数，表示方案总数，由于这个题答案可能很大，只要输出答案 $\bmod{19921107}$。

1 6

18

数据规模与约定

对于 $100\%$ 的数据，$1\le p\le10$，$1\le q\le10^9$，$p$ 和 $q$ 互质