q_pow()为快速幂。
right_side[]为方程组等号右边。

void elimination(int n)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            if (matrix[j][i])
            {
                for (int k = i; k <= n; k++)
                {
                    swap(matrix[i][k], matrix[j][k]);
                }
                swap(right_side[i], right_side[j]);
                break;
            }
        }

        for (int j = i + 1; j <= n; j++)
        {
            if (matrix[j][i])
            {
                long long delta = matrix[j][i] * q_pow(matrix[i][i], mod - 2) % mod;
                for (int k = i; k <= n; k++)
                {
                    matrix[j][k] -= matrix[i][k] * delta % mod;
                    if (matrix[j][k] < 0) matrix[j][k] += mod;
                }
                right_side[j] -= right_side[i] * delta % mod;
                if (right_side[j] < 0) right_side[j] += mod;
            }
        }
    }

    for (int i = n; i >= 1; i--)
    {
        for (int j = i + 1; j <= n; j++)
        {
            right_side[i] -= right_side[j] * matrix[i][j] % mod;
            if (right_side[i] < 0) right_side[i] += mod;
        }
        right_side[i] = right_side[i] * q_pow(matrix[i][i], mod - 2) % mod;
    }
}