ISL 2013 C7

Let $n \geqslant 2$ be an integer. Consider all circular arrangements of the numbers $0,1, \ldots, n$; the $n+1$ rotations of an arrangement are considered to be equal. A circular arrangement is called beautiful if, for any four distinct numbers $0 \leqslant a, b, c, d \leqslant n$ with $a+c=b+d$, the chord joining numbers $a$ and $c$ does not intersect the chord joining numbers $b$ and $d$. Let $M$ be the number of beautiful arrangements of $0,1, \ldots, n$. Let $N$ be the number of pairs $(x, y)$ of positive integers such that $x+y \leqslant n$ and $\operatorname{gcd}(x, y)=1$. Prove that $$M=N+1$$ (Russia)