从前，有一位不同寻常的象（bishop）住在一块不同寻常的棋盘上。这块棋盘之所以不同寻常，是因为它的大小是任意的 $N \times M$。这位象之所以不同寻常，是因为它被放置在棋盘的一个角上。它在那里站了很久，感到很无聊。于是，它决定随心所欲地开始一段旅程。众所周知，象的视线总是沿着对角线方向。当到达棋盘边缘时，象会转动 90 度并继续移动。以此类推。只有当象再次到达某个（第一个遇到的）角时，它才会停止移动。
请问在它绕着 $N \times M$ 的棋盘旅行的过程中，一共访问了多少个不同的格子？
输入的第一行包含两个整数 $N$ 和 $M$，表示棋盘的大小。
$1 < N \le 10^{18}$ $1 < M \le 10^{18}$
输出一行，包含一个整数，表示访问过的格子总数对质数 $10^{18} + 9$ 取模后的结果。
15 22
42
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: