Let \(E = \{ (i, j) \, | \, 1 \leq i \lt j \leq N, i \in \mathbb{Z}, j \in \mathbb{Z} \}\). For \(S \subset E\), let \(f(S)\) be the following value:

• Consider an undirected graph with \(N\) vertices that has an edge between vertices \((i, j9\) only if \((i, j) \in S\). The value is the number of ways to determine \(A_i\) such that \(1 \leq A_i \leq M\), \(A_i\) is a multiple of \(D_i\), and for each connected component, the values of \(A_i\) corresponding to the vertices of the component should be equal.

By the inclusion-exclusion principle, we have \( \displaystyle \sum_{S \in E} f(S) (-1)^{|S|} \).

For a set of vertices \(T\), let \(g(T) = \displaystyle \left\lfloor \frac{M}{\mathrm{lcm}_{i \in T} D_i} \right\rfloor\). Also, let \(h(n)\) be the sum of \(1\) or \(-1\) for each subset of \(\frac{n(n-1)}{2}\) edges that makes entire graph connected, which takes the value \(1\) if the number of edges of the subset is even, or \(-1\) if odd.

\(g(T)\) can be precomputed in a total of \(O(2^N)\) time. For \(h(n)\) we can see that \(h(n) = (-1)^{n - 1}(n - 1)!\) based on the following observations:

• \(h(1) = 1\).
• If \(n \geq 2\), then the number of ways to choose even number of edges and odd number of edges are the same, as long as it should not necessarily be connected. Let \(T\) be the connected component that Vertex \(1\) belongs. We consider eliminating the cases where \(T \neq \{1, \dots, n \}\). If the number of elements of \(T \neq \{1, \dots, n \}\) is greater than or equal to \(2\), then the number of ways to choose even number of edges and odd number of edges is the same, so it can be ignored; we only have to eliminate \(n-1\) cases where the number of elements in \(T\) is \(n-1\), so \(h(n) = -(n - 1)h(n - 1)\).

The sum of \( f(S) (-1)^{|S|} \) over all set of edges \(S\) that divides the vertices into \(k\) connected components \(T_1, \dots, T_k\) is equal to

\[\displaystyle \prod_{i = 1}^k g(T_k) h(|T_k|). \]

For a set of vertices \(T\), let us denote by \(\mathrm{dp}_T\) the sum of the value above over all the ways to divide \(T\) into connected components. Then the desired value is \(\mathrm{dp}_{\{1, \dots, N\}}\).

Suppose that \(\mathrm{dp}_{T'}\) is already known for every proper subset \(T'\) of \(T\). Fix a vertex \(u\) in \(T\) and divide into cases depending on the connected component that \(u\) belongs; then \(\mathrm{dp}_T\) can be found as follows (where \(\mathrm{dp}_{\empty} = 1\)):

\[\displaystyle \mathrm{dp}_T = \sum_{T' \sub T, u \in T'} g(T') h(|T'|) \times \mathrm{dp}_{T \setminus T'}\]

Therefore, \(\mathrm{dp}\) can be computed in a total of \(O(3^N)\) time, so the problem has been solved.

Sample code