Calculate the value of the sum: n mod 1 + n mod 2 + n mod 3 + ... + n mod m. As the result can be very large, you should print the value modulo 10^9 + 7 (the remainder when divided by 10^9 + 7).

The modulo operator a mod b stands for the remainder after dividing a by b. For example 10 mod 3 = 1.


-----Input-----

The only line contains two integers n, m (1 ≤ n, m ≤ 10^13) — the parameters of the sum.


-----Output-----

Print integer s — the value of the required sum modulo 10^9 + 7.


-----Examples-----
Input
3 4

Output
4

Input
4 4

Output
1

Input
1 1

Output
0

Source: codeforces | Difficulty: HARD
Tags: Mathematics

Number theory

Implementation


Solutions:
from functools import cmp_to_key
from collections import deque, Counter
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def si():
	return str(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def lsi():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)
MOD = 10 ** 9 + 7
maxN = 5
FACT = [0] * maxN
INV_FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def inverseFactorials():
	n = len(INV_FACT)
	INV_FACT[n - 1] = inverse(FACT[n - 1])
	for i in range(n - 2, -1, -1):
		INV_FACT[i] = multiply(INV_FACT[i + 1], i + 1)

def coeffBinom(n, k):
	if n < k:
		return 0
	return multiply(FACT[n], multiply(INV_FACT[k], INV_FACT[n - k]))

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path

def p1(n, m, r):
	s = 0
	for i in range(1, min(m, r) + 1):
		s = add(s, n % i)
	return s

def p2(n, m, r):
	s = 0
	for i in range(1, r + 1):
		left = max(n // (i + 1) + 1, r + 1)
		right = min(n // i, m)
		if left <= right:
			ml = n % left
			mr = n % right
			k = (ml - mr) // i
			s = add(s, multiply(mr, k + 1))
			s = add(s, multiply(i, k * (k + 1) // 2))
	return s

def p3(n, m):
	if m >= n:
		return (m - n) % MOD * (n % MOD) % MOD
	return 0
(n, m) = li()
r = int(n ** 0.5)
f1 = p1(n, m, r)
f2 = p2(n, m, r)
f3 = p3(n, m)
s = (f1 + f2 + f3) % MOD
print(s % MOD)


def sub(a, b):
	if a - b < 0:
		return a - b + MOD
	else:
		return a - b
MOD = 10 ** 9 + 7
(n, m) = [int(x) for x in input().split()]
ans = n * m % MOD
k = min(n, m)
d1 = 1
while d1 * d1 <= n:
	if d1 <= k:
		ans = sub(ans, n // d1 * d1 % MOD)
	d1 += 1
d = 1
while d * d <= n:
	r = min(k, n // d)
	l = max(d1, n // (d + 1) + 1)
	if l <= r and l <= k:
		s = (l + r) * (r - l + 1) // 2
		ans = sub(ans, d * s % MOD)
	d += 1
print(ans)


from math import sqrt

def main():
	(n, m) = map(int, input().split())
	(ans, cur) = (0, 2)
	if m >= n:
		ans = n * (m - n)
		m = n - 1
	t = min(int(sqrt(n)) + 1, m)
	while cur <= t:
		ans += n % cur
		cur += 1
	while cur <= m:
		div = n // cur
		nxt = min(n // div, m)
		sub = nxt - cur + 1
		ans += n % cur * sub - div * sub * (sub - 1) // 2
		cur = nxt + 1
	print(ans % 1000000007)
main()


import math
MOD = int(1000000000.0 + 7)
(N, M) = map(int, input().split())
sn = int(math.sqrt(N))
ans = N * M % MOD
for i in range(1, min(sn, M) + 1, 1):
	ans -= N // i * i
ans %= MOD
if N // (sn + 1) > M:
	exit(print(ans))

def s(x):
	return x * (x + 1) // 2
for f in range(N // (sn + 1), 0, -1):
	if N // f > M:
		ans -= f * (s(M) - s(N // (f + 1)))
		break
	ans -= f * (s(N // f) - s(N // (f + 1)))
ans %= MOD
if ans < 0:
	ans += MOD
print(ans)


from math import sqrt
(n, m) = map(int, input().split())
t = min(int(sqrt(n)) + 1, m)
i = 2
mod = 10 ** 9 + 7
ans = 0
while i <= t:
	ans += n % i
	i += 1
ans %= mod
i = t + 1
while i <= min(n, m):
	d = n // i
	t = min(m, n // d)
	cnt = t - i + 1
	x = n % i * cnt - d * ((cnt - 1) * cnt >> 1)
	ans = (ans + x) % mod
	i = t + 1
if i <= m:
	ans = (ans + n * (m - i + 1)) % mod
print(ans)


import math
(n, m) = map(int, input().split())
mod = pow(10, 9) + 7
ans = 0
if n < m:
	ans = n * (m - n) % mod
	m = n
ns = int(math.sqrt(n))
x = [0] * ns
f = 1
for i in range(ns):
	if i + 1 > m:
		f = 0
		break
	x[i] = n // (i + 1)
	ans += n - x[i] * (i + 1)
	ans %= mod
for i in range(ns + 1, max(ns + 1, x[-1] + 1)):
	ans += n % i
	ans %= mod
if f:
	for i in range(ns - 1):
		if x[i + 1] >= m:
			continue
		c = x[i] - x[i + 1]
		ans += (n - x[i] * (i + 1)) * c + (i + 1) * c * (c - 1) // 2
		ans %= mod
		if x[i] >= m > x[i + 1]:
			c = x[i] - m
			ans -= (n - x[i] * (i + 1)) * c + (i + 1) * c * (c - 1) // 2
			ans %= mod
print(ans)


from math import floor

def range_sum(low, up):
	return up * (up + 1) // 2 - low * (low + 1) // 2
mod = int(1000000000.0 + 7)
(n, m) = map(int, input().split())
(ans, sqrt_n) = (m * n, int(floor(n ** 0.5)))
temp = 0
for i in range(1, sqrt_n + 1):
	up = n // i
	low = n // (i + 1)
	up = min(up, m)
	if up < low:
		continue
	temp1 = range_sum(low, up)
	temp += temp1 * i
for i in range(1, sqrt_n + 1):
	if m < i:
		break
	if n // i != i:
		temp += n // i * i
print((ans - temp) % mod)