Задача . D. Подсчет массивов

Рассмотрим массив \(a\) длины \(n\), элементы которого пронумерованы от \(1\) до \(n\). Можно удалить \(i\)-й элемент из \(a\), если \(gcd(a_i, i) = 1\), где \(gcd\) обозначает наибольший общий делитель. После того, как элемент удаляется, те элементы, которые были справа от него, сдвигаются на одну позицию влево.

Массив \(b\) из \(n\) элементов, для которых выполняется \(1 \le b_i \le n - i + 1\), называется последовательностью удалений для массива \(a\), если можно удалить все элементы \(a\) в следующем порядке: сначала удалить \(b_1\)-й элемент, затем \(b_2\)-й, ..., затем \(b_n\)-й. Например, пусть \(a = [42, 314]\):

• \([1, 1]\) — последовательность удалений: когда вы удаляете \(1\)-й элемент массива, условие \(gcd(42, 1) = 1\) соблюдаются, и массив становится \([314]\); когда вы снова удаляете \(1\)-й элемент, условие \(gcd(314, 1) = 1\) соблюдается, и массив становится пустым.
• \([2, 1]\) не является последовательностью удалений: когда вы пытаетесь удалить \(2\)-й элемент, условие \(gcd(314, 2) = 1\) не выполняется.

Назовем массив неоднозначным, если у него хотя бы две последовательности удалений. Например, массив \([1, 2, 5]\) — неоднозначный: у него есть последовательности удалений \([3, 1, 1]\) и \([1, 2, 1]\). Массив \([42, 314]\) не является неоднозначным: единственная последовательность удалений для него — это \([1, 1]\).

Вам даны два числа \(n\) и \(m\). Посчитайте количество неоднозначных массивов \(a\), таких, что длина \(a\) от \(1\) до \(n\), а элементы \(a_i\) — целые числа от \(1\) до \(m\).