Even the last sum can be calculated in $$$O(1)$$$

Wow, this idea is very elegant :o Thanks for sharing

Wow, that's really pretty neat n elegant bro, great!!

Hey, sorry for late reply bro, here's my code:

//Nightmare05
#include<bits/stdc++.h>

using namespace std;

#define sp << " " <<
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define int long long
#define double long double
#define INF (1e18+13)
//#define PI 3.1415926535898

int power(int p,int j)
{
    int res=1;
    p=p%mod;
    while(j>0)
    {
        if(j&1)
            res=(res*p)%mod;
        j=j>>1;
        p=(p*p)%mod;
    }
    return res;
}


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dice(int d,int p)
{
    uniform_int_distribution<int> uid(d,p);//specify l and s.
    return uid(rng) ;
}
/*
int read()
{
       int cc = getc(stdin);
       for (;cc < '0' || cc > '9';)  cc = getc(stdin);
       int ans = 0;
       for (;cc >= '0' && cc <= '9';)
       {
          ans = ans * 10 + cc - '0';
          cc = getc(stdin);
       }
      return ans;
}

inline void print(int n)
{
  if (n == 0)
  {
    putchar('0');
    putchar('\n');
  }
  else if (n == -1)
  {
    putchar('-');
    putchar('1');
    putchar('\n');
  }
  else
  {
    char buf[20];
    buf[19] = '\n';
    int i = 18;
    while (n)
    {
      buf[i--] = n % 10 + '0';
      n /= 10;
    }
    while (buf[i] != '\n')
      putchar(buf[++i]);
  }
}

int n;

vector<vector<int>> mat_mul(vector<vector<int>> a,vector<vector<int>> b)
{
    int n=2;
    vector<vector<int>> ans2(n,vector<int>(n,0));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int k=0;k<n;k++)
            {
                ans2[i][j]+=((a[i][k]*b[k][j])%mod);
                ans2[i][j]%=mod;
            }
        }
    }
    return ans2;
}

vector<vector<int>> pow_mat(vector<vector<int>> mat_a,int p)
{
    if(p==1)
        return mat_a;
    vector<vector<int>> temp=pow_mat(mat_a,p/2);
    vector<vector<int>> res=mat_mul(temp,temp);
    if(p&1)
        res=mat_mul(res,mat_a);
    return res;
}
*/

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
}

vector<int> multiply(vector<int> const& a, vector<int> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size())
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<int> result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("elimination_validation_input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    vector<int> a(n,0);
    for(int i=1;i<n;i++)
        a[(i*i)%n]++;
    vector<int> b=multiply(a,a);
    for(int i=n;i<b.size();i++)
        b[i%n]+=b[i];
    int dp=0;
    for(int i=0;i<n;i++)
    {
        dp+=a[i]*b[i];
        dp+=a[i]*a[(2*i)%n];
    }
    cout << dp/2;
    return 0;
}

PROBLEM STATEMENT

Sample Input 1
4
Sample Output 1
5
Explanation: required triplets are:
(1, 2, 1)
(1, 2, 3)
(2, 2, 2)
(2, 3, 1)
(2, 3, 3)
Sample Input 2
7
Sample Output 2
18

PS: Sorry for these huge screenshots, I don't know why spoilers are not working