405865: GYM102136 G A Bishop's Journey

Once upon a time there was an unusual bishop who lived on an unusual chess board. The board was unusual because it was of an arbitrary size N × M. The bishop was unusual because it was placed in the corner field of the board. It stood there for a long time and got bored. And so it decided to go on a journey wherever its eyes lead him. As is well known, the eyes of bishops lead them diagonally. Having reached the edge of the board, the bishop turned through 90 degrees and continued to move. And so on. The bishop had stopped only when again got into some (first available) corner.

How many unique fields did it visit during his journey around the N × M board?

The first and only line contains integers N and M — the chess board sizes.

The single line contains the only number —required number of visited fields by prime modulo 10¹⁸ + 9.

15 22

42