using ll = long long;

// caculate number of points below (a/c)x+(b/c)
// count of "STRICKTLY" below of the line
// count of "STRICKTLY" upper of the X axis
// find number in range [0, n)
// a must not be negative
// be carefull of overflow

ll calc(ll a,ll b,ll c,ll n){
    if(!n)return 0;
    ll tmp=a/c*n*(n-1)/2;
    tmp+=b/c*n;
    return tmp+calc(c,(a*n+b)%c,a%c,((a%c)*n+b%c)/c);
}