A frog is initially at position $0$ on the number line. The frog has two positive integers $a$ and $b$. From a position $k$, it can either jump to position $k+a$ or $k-b$.

Let $f(x)$ be the number of distinct integers the frog can reach if it never jumps on an integer outside the interval $[0, x]$. The frog doesn't need to visit all these integers in one trip, that is, an integer is counted if the frog can somehow reach it if it starts from $0$.

Given an integer $m$, find $\sum_{i=0}^{m} f(i)$. That is, find the sum of all $f(i)$ for $i$ from $0$ to $m$.


-----Input-----

The first line contains three integers $m, a, b$ ($1 \leq m \leq 10^9, 1 \leq a,b \leq 10^5$).


-----Output-----

Print a single integer, the desired sum.


-----Examples-----
Input
7 5 3

Output
19

Input
1000000000 1 2019

Output
500000001500000001

Input
100 100000 1

Output
101

Input
6 4 5

Output
10



-----Note-----

In the first example, we must find $f(0)+f(1)+\ldots+f(7)$. We have $f(0) = 1, f(1) = 1, f(2) = 1, f(3) = 1, f(4) = 1, f(5) = 3, f(6) = 3, f(7) = 8$. The sum of these values is $19$.

In the second example, we have $f(i) = i+1$, so we want to find $\sum_{i=0}^{10^9} i+1$.

In the third example, the frog can't make any jumps in any case.

Difficulty: interview

Starter code:

Solutions:
import math
m,a,b=map(int,input().split())
g=math.gcd(a,b)
a1=a//g
b1=b//g
alls=g*(a1+b1-1)
dists=[0]+[-1]*(a1+b1-1)
dist=0
far=0
while dist!=b1:
    if dist<b1:
        dist+=a1
        far=max(dist,far)
    else:
        dist-=b1
    if dists[dist]==-1:
        dists[dist]=far
tot=0
for i in range(a1+b1):
    if i*g<=m and dists[i]*g<=m:
        tot+=(m+1-dists[i]*g)
if alls<m:
    mod=m%g
    times=m//g
    diff=times-a1-b1
    tot1=g*(diff*(diff+1)//2)+(mod+1)*(diff+1)
    tot+=tot1
print(tot)

from math import gcd

m,a,b = list(map(int,input().split()))

g = gcd(a,b)

vis = [0]*(a+b+1)
vis[0] = 1

nvis = 1

count = 0
last = 0
t = 0
while True:
    #print(t, vis)
    if t >= b:
        #print('back')
        t -= b
        if vis[t]:
            break
        vis[t] = 1
        nvis += 1
    else:
        t += a
        if t > m:
            break
        if t > last:
            #print('forward', t - last, 'with', nvis)
            count += (t - last)*nvis
            last = t
        if vis[t]:
            break
        vis[t] = 1
        nvis += 1
    #print(nvis,count)
    #print('---')

if t > m:
    # we're done
    count += (m - last + 1)*nvis
else:
    def sumto(n):
        whole = n//g + 1
        r = whole*(whole+1)//2 * g
        corr = whole * (g-1 - (n%g))
        r -= corr
        return r

    #S = 0
    #for i in range(last, m+1):
    #    S += i//g + 1
    #count += S
    #assert S == sumto(m) - sumto(last-1)

    count += sumto(m) - sumto(last-1)

#print(vis)
print(count)


from collections import deque
def gcd(a, b):
    b = abs(b)
    while b != 0:
        r = a%b
        a,b = b,r
    return a

M, A, B = list(map(int, input().split()))
X = [1]+[0]*(10**6)
Y = [0]
s = 1
t = 1
g = gcd(A, B)
for N in range(1, M+1):
    if N >= A+B+g and (M-N+1) % g == 0:
        ss = Y[N-1]-Y[N-g-1]
        dd = (Y[N-1]-Y[N-2]) - (Y[N-g-1]-Y[N-g-2])
        t += ss*(M-N+1)//g + dd*g*((M-N+1)//g)*((M-N+1)//g+1)//2
        break
    elif N >= A and X[N-A]:
        que = deque([N])
        X[N] = 1
        s += 1
        while len(que):
            i = deque.pop(que)
            if i >= B and X[i-B] == 0:
                deque.append(que, i-B)
                X[i-B] = 1
                s += 1
            if i + A < N and X[i+A] == 0:
                deque.append(que, i+A)
                X[i+A] = 1
                s += 1
    t += s
    Y.append(t)
print(t)



M, a, b = map(int, input().split())
mod = 10**9+7
D = [mod]*a
maxi = 0
D[0] = 0
Q = [0]
def f(x, i):
    t = (x+1-i)//a
    r = (x+1-i)%a
    return a*t*(t+1)//2+r*(t+1)

while Q:
    q = Q.pop()
    D[q] = maxi
    k = max(0, -((-(b-q))//a))
    maxi = max(maxi, q+k*a)
    if D[(q-b)%a] == mod and maxi <= M:
        Q.append((q-b)%a)
ans = 0
for i, d in enumerate(D):
    if d > M:
        continue
    ans += f(M, i) - f(d-1, i)
print(ans)

import sys
import math
input = sys.stdin.readline

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

m,a,b=list(map(int,input().split()))

GCD=gcd(a,b)


#when a>b,

MODLIST=[-1]*a

NOWMAX=a
NOW=a
MODLIST[0]=a
while True:
    
    while NOW-b>0 and MODLIST[(NOW-b)%a]==-1:
        NOW-=b
        MODLIST[NOW]=NOWMAX

    NOW+=a
    NOWMAX=max(NOW,NOWMAX)

    if MODLIST[(NOW-b)%a]!=-1:
        break

ANS=m+1#0
MAX=max(MODLIST)
for i in range(1,min(m+1,MAX)):
    if MODLIST[i%a]==-1:
        continue
    ANS+=max((m+1-max(MODLIST[i%a],i)),0)

    #print(ANS)


if MAX<=m:
    ANS+=(m-MAX+1+(m-m//GCD*GCD)+1)*((m//GCD*GCD-MAX)//GCD+1)//2

print(ANS)
    


    
    
    


from math import gcd
m, a, b = list(map(int, input().split()))
last, x = 0, gcd(a, b)
s = [1]*(a+b+1)
q1, ans = 0, 1
max1, s[0] = [[0, 1]], 0
while q1 < a+b:
    if q1 > b and s[q1-b]:
        ans += 1
        q1 -= b
        s[q1] = 0
    else:
        q1 += a
        if q1 > last:
            max1.append([q1, ans])
            last = q1
        if s[q1]:
            ans += 1
            s[q1] = 0
ans1 = q1 = 0
for q in range(min(m+1, a+b)):
    if max1[q1+1][0] == q:
        q1 += 1
    ans1 += max1[q1+1][1]
if m >= a+b:
    ans1 += (m//x+1)*(m % x+1)
    m -= m % x+1
    p, t = (a+b)//x, (m-a-b)//x
    ans1 += (t+1)*(t+2)//2*x
    ans1 += p*(t+1)*x
print(ans1)


import math
m,a,b=list(map(int,(input().split())))
vis=[-1]*(a+b+5)
now=0
maxd=0
while True:
    vis[now]=maxd
    #print(now,maxd)
    if now>=b:
        now-=b
    else:
        now+=a
    if now==0:
        break
    maxd=max(maxd,now)
ans=0
#for i in range(0,a+b):
    #print(vis[i])
for i in range(0,a+b):
    if vis[i]!=-1:
        ans+=max(0,m-vis[i]+1)
rest=m-(a+b)+1
if m>=a+b:
    g=math.gcd(a,b)
    tmp=(rest//g)*g
    fir=rest-tmp
    lst=rest
    cnt=tmp//g+1
    ans+=(fir+lst)*cnt//2
print(int(ans))


import math
m,a,b=list(map(int,(input().split())))
vis=[-1]*(a+b+5)
now=0
maxd=0
while True:
    vis[now]=maxd
    #print(now,maxd)
    if now>=b:
        now-=b
    else:
        now+=a
    if now==0:
        break
    maxd=max(maxd,now)
ans=0
#for i in range(0,a+b):
    #print(vis[i])
for i in range(0,a+b):
    if vis[i]!=-1:
        ans+=max(0,m-vis[i]+1)
rest=m-(a+b)+1
if m>=a+b:
    g=math.gcd(a,b)
    tmp=(rest//g)*g
    fir=rest-tmp
    lst=rest
    cnt=tmp//g+1
    ans+=(fir+lst)*cnt//2
print(int(ans))


import math
M, A, B = list(map(int, input().split()))
bound = [10**9 + 7]*(A + B)
l, r = 0, 0
while True:
    bound[l] = r
    if l >= B:
        l -= B
    else:
        l += A
    r = max(r, l)
    if l == 0:
        break

ans = 0
for i in range(0, A + B):
    if bound[i] <= M:
        ans += M - bound[i] + 1

rem = M - (A + B) + 1
if M >= (A + B):
    g = math.gcd(A, B)
    up = (rem // g) * g
    lo = rem - up
    cnt = up // g + 1
    ans += (lo + rem) * cnt // 2
print(ans)


import math
M, A, B = map(int, input().split())
bound = [10**9 + 7]*(A + B)
l, r = 0, 0
while True:
    bound[l] = r
    if l >= B:
        l -= B
    else:
        l += A
    r = max(r, l)
    if l == 0:
        break

ans = 0
for i in range(0, A + B):
    if bound[i] <= M:
        ans += M - bound[i] + 1

rem = M - (A + B) + 1
if M >= (A + B):
    g = math.gcd(A, B)
    up = (rem // g) * g
    lo = rem - up
    cnt = up // g + 1
    ans += (lo + rem) * cnt // 2
print(ans)