Among the \(\frac{M(M-1)}{2}\) pairs of lines, you are asked to count those that intersect; but we will consider the complementary events and count the pairs that do not intersect. The answer can be found as the count subtracted from \(\frac{M(M-1)}{2}\).

Two lines do not intersect if and only if they are parallel. How can we count pairs of parallel lines?

If lines \(L_1\) and \(L_2\) are parallel, and lines \(L_2\) and \(L_3\) are parallel, then lines \(L_1\) and \(L_3\) are also parallel. This is also due to the property that lines with the same slope are all parallel to each other. Conversely, any two lines with different slopes always intersect. Thus, if there are \(k\) lines with the same slope, then there are \(\frac{k(k-1)}{2}\) pairs of parallel lines.

Therefore, the problem can be solved by classifying the \(M\) lines by their slopes. We will now describe how we can actually classify them.

In fact, they can be classified by \((A_i+B_i) \bmod N\). This is because, for a line that passes through points \(A_i\) and \(B_i\), the line passing through the \(k\)-th point counted clockwise from point \(A_i\) and the \(k\)-th point counted counterclockwise from point \(B_i\) is parallel to the line passing through points \(A_i\) and \(B_i\).

On implementation, make sure not to use 32-bit integer types, as it may cause an overflow.

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> cnt(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        cnt[(a + b) % n]++;
    }
    ll ans = (ll)m * (m - 1) / 2;
    for (auto e : cnt) {
        ans -= e * (e - 1) / 2;
    }
    cout << ans << endl;
}