Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Compute:
floor[1*e] + floor[2*e] + floor[3*e] + ... + floor[n*e],
where floor[x] is the largest integer that is not greater than x, and e is Euler's number: 2.7182818284...

------ Input ------ 

A single line which contains a single integer: n.

------ Output ------ 

A single line which contains a single integer which should be the answer.

------ Constraints ------ 

1 ≤ n ≤ 10^{4000}

------ Subtasks ------ 

$Subtask #1 (50 points): 1 ≤ n ≤ 10^{100}
$$Subtask #2 (50 points): Original constraints.$

----- Sample Input 1 ------ 
3
----- Sample Output 1 ------ 
15
----- explanation 1 ------ 

floor[1*e] = floor[2.71828..] = 2.
floor[2*e] = floor[5.43656..] = 5.
floor[3*e] = floor[8.15484..] = 8.
So the answer is 2+5+8=15.

Note
Source code limit is 1000 bytes.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics


Solutions:
import sys
N = int(input())
sys.setrecursionlimit(1000000)

def t(l, r):
	if l + 1 == r:
		return (1, l)
	else:
		m = (l + r) // 2
		e = t(l, m)
		d = t(m, r)
		return (e[0] * d[1] + d[0], e[1] * d[1])

def calc(a, b, n):
	if n == 0:
		return 0
	k = a // b
	a -= k * b
	m = a * n // b
	return k * (n * (n + 1) >> 1) + m * n - calc(b, a, m)
print(N * (N + 1) + calc(*t(2, 3505), N))


N = int(input())

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

def t(l, r):
	if l + 1 == r:
		return (1, l)
	else:
		m = (l + r) // 2
		e = t(l, m)
		d = t(m, r)
		return (e[0] * d[1] + d[0], e[1] * d[1])
k = t(2, 5000)
g = gcd(k[0], k[1])
k = (k[0] // g, k[1] // g)

def calc(a, b, n):
	seq = []
	(x, y, N) = (a, b, n)
	while True:
		if n == 0:
			seq.append((1, 0))
			break
		elif a >= b:
			temp = n * (n + 1) // 2 * (a // b)
			if a % b > 0:
				seq.append((temp, 1))
				a = a % b
			else:
				seq.append((temp + n + 1, 0))
				break
		else:
			seq.append(((n + 1) * (n * a // b + 1) + n // b + 1, -1))
			(a, b, n) = (b, a, n * a // b)
	ans = seq.pop()[0]
	while len(seq) > 0:
		last = seq.pop()
		ans = ans * last[1] + last[0]
	return ans
print((N - 1) * (N + 1) + calc(*k, N))


import sys
import math
line = lambda : list((int(x) for x in input().split()))
MOD = int(1000000000.0 + 7)
MAXN = 4100
a = [0 for i in range(MAXN)]
p = [0 for i in range(MAXN)]
q = [0 for i in range(MAXN)]
t = [0 for i in range(MAXN)]

def build():
	for i in range(MAXN):
		if i % 3 < 2:
			a[i] = 1
		else:
			a[i] = i // 3 * 2 + 2
	a[0] = 2
	p[MAXN - 1] = a[MAXN - 1]
	q[MAXN - 1] = 1
	for k in reversed(range(MAXN - 1)):
		p[k] = p[k + 1] * a[k] + q[k + 1]
		q[k] = p[k + 1]

def solve():
	build()
	t[0] = int(input())
	for i in range(MAXN - 1):
		t[i + 1] = t[i] * q[i + 1] // p[i + 1]
	res = 0
	for i in reversed(range(MAXN - 1)):
		res *= -1
		res += t[i] * t[i + 1]
		res += t[i] * (t[i] + 1) // 2 * a[i]
	print(res)
solve()
exit(0)


import sys

def calc(p, q, n):
	if n == 0:
		return 0
	k = p // q
	p -= k * q
	h = n * p // q
	return k * n * (n + 1) // 2 + n * h - calc(q, p, h)
sys.setrecursionlimit(100500)
n = int(input())
p = 1
q = 1
for i in range(1, 3500):
	p *= i
	q *= i
	p += 1
print(calc(p, q, n))


import time
import sys

def calc(p, q, n):
	if n == 0:
		return 0
	a = p // q - 1
	po = p
	p -= q * a
	m = n * (p - q) // q
	t = m + n
	return a * n * (n + 1) // 2 + t * (t + 1) // 2 - calc(p, p - q, m)
sys.setrecursionlimit(100500)
n = int(input())
p = 1
q = 1
for i in range(1, 3500):
	p *= i
	q *= i
	p += 1
print(calc(p, q, n))


def a(n):
	if n % 3 == 2:
		return (n // 3 + 1) * 2
	if n == 0:
		return 2
	return 1
v = [1]

def k(n):
	(c, d) = (0, 1)
	for i in range(n):
		(c, d) = (d, c + d * a(i + 1))
		v.append(d)
	return d
w = [2]

def h(n):
	(c, d) = (1, 2)
	for i in range(n):
		(c, d) = (d, c + d * a(i + 1))
		w.append(d)
	return d
x = k(4000)
y = h(4000)

def q(n):
	for i in range(0, n, 2):
		if v[i + 2] > n:
			return v[i]

def p(n):
	for i in range(0, n, 2):
		if v[i + 2] > n:
			return w[i]

def t(n):
	for i in range(1, n, 2):
		if v[i + 2] > n:
			return v[i]

def u(n):
	for i in range(1, n, 2):
		if v[i + 2] > n:
			return w[i]

def nl(n):
	if n == 0 or n == 1:
		return 0
	if q(n) < t(n):
		d = n // t(n)
		r = n % t(n)
		s = d * (u(n) - 1) * (t(n) - 1) // 2 + (d - 1) * d * u(n) * t(n) // 2 + r * u(n) * d - d + nl(r)
		if r == 0:
			return s + 1
		return s
	d = n // q(n)
	r = n % q(n)
	return d * (p(n) - 1) * (q(n) - 1) // 2 + (d - 1) * d * p(n) * q(n) // 2 + r * p(n) * d + nl(r)
import sys
sys.setrecursionlimit(10000)
line = sys.stdin.readline()
print(nl(1 + int(line)))


p = [1, 2, 3, 8]
q = [0, 1, 1, 3]
n = int(input())
i = 0
while q[-2] <= n:
	a = 1
	if i % 3 == 2:
		a = 2 * (i // 3 + 2)
	p.append(a * p[-1] + p[-2])
	q.append(a * q[-1] + q[-2])
	i += 1

def sa(b, i, m):
	res = m * b * p[i]
	if i & 1:
		res += (b * p[i] * q[i] - q[i] + p[i] + 1) * b // 2
	else:
		res += (b * p[i] * q[i] - q[i] + p[i] - 1) * b // 2
	return res
ans = 0
i = len(p) - 1
while 1:
	if q[i] <= n and q[i + 1] > n:
		if q[i] == n:
			ans += sa(1, i, 0)
			n = 0
			break
		else:
			b = n // q[i]
			m = n % q[i]
			ans += sa(b, i, m)
			n = m
	i -= 1
print(ans)


p = [1, 2, 3, 8]
q = [0, 1, 1, 3]
n = int(input())
j = 0
for i in range(0, 4100):
	a = 1
	if i % 3 == 2:
		a = 2 * (i // 3 + 2)
	p.append(a * p[-1] + p[-2])
	q.append(a * q[-1] + q[-2])
	if q[i] > n:
		j = i - 1
		break

def sa(b, i, m):
	res = m * b * p[i]
	if i & 1:
		res += (b * p[i] * q[i] - q[i] + p[i] + 1) * b // 2
	else:
		res += (b * p[i] * q[i] - q[i] + p[i] - 1) * b // 2
	return res
ans = 0
i = j
while 1:
	if q[i] <= n and q[i + 1] > n:
		if q[i] == n:
			ans += sa(1, i, 0)
			n = 0
			break
		else:
			b = n // q[i]
			m = n % q[i]
			ans += sa(b, i, m)
			n = m
	i -= 1
print(ans)


p = [0, 1, 2]
q = [0, 1, 3]
n = int(input())
for i in range(0, 4100):
	a = 1
	if i % 3 == 2:
		a = 2 * (i // 3 + 2)
	p.append(a * p[-1] + p[-2])
	q.append(a * q[-1] + q[-2])

def sa(b, i, m):
	res = m * b * p[i]
	if i & 1:
		res += (b * p[i] * q[i] - q[i] + p[i] - 1) * b // 2
	else:
		res += (b * p[i] * q[i] - q[i] + p[i] + 1) * b // 2
	return res
ans = n * (n + 1)
for i in range(4000, 0, -1):
	if q[i] <= n and q[i + 1] > n:
		if q[i] == n:
			ans += sa(1, i, 0)
			n = 0
		else:
			b = n // q[i]
			m = n % q[i]
			ans += sa(b, i, m)
			n = m
print(ans)


import math
p = [0, 1, 2]
q = [0, 1, 3]
n = int(input())
a = [0, 1, 2]
for i in range(1, 1500):
	a.append(1)
	a.append(1)
	a.append(2 * (i + 1))
for i in range(3, 4005):
	p.append(a[i] * p[i - 1] + p[i - 2])
	q.append(a[i] * q[i - 1] + q[i - 2])

def sa(b, i, m):
	res = m * b * p[i]
	if i & 1:
		res += (b * p[i] * q[i] - q[i] + p[i] - 1) * b // 2
	else:
		res += (b * p[i] * q[i] - q[i] + p[i] + 1) * b // 2
	return res
ans = n * (n + 1)
for i in range(4000, 0, -1):
	if q[i] <= n and q[i + 1] > n:
		if q[i] == n:
			ans += sa(1, i, 0)
			n = 0
		else:
			b = n // q[i]
			m = n - b * q[i]
			ans += sa(b, i, m)
			n = m
print(ans)


def Solve(a, b, c, n):
	res = 0
	op = 1
	while True:
		if a == 0:
			return res + op * (b // c * n)
		elif b < 0:
			m = (-b + c - 1) // c
			b = b + m * c
			res -= op * m * n
		elif a >= c:
			res += op * (a // c) * (n * (n + 1) // 2)
			a = a % c
		else:
			m = (a * n + b) // c
			res += op * (n + 1) * m
			b = a - b - 1
			(a, c) = (c, a)
			n = m
			op = -op
n = int(input())
C = 1
A = 1
lim = 3000
for i in range(1, lim):
	C *= i
for i in range(1, lim):
	A = A * i + 1
print(Solve(A, 0, C, n))


import sys
sys.setrecursionlimit(1000000000)

def Solve(a, b, c, n):
	if a == 0:
		return b // c * n
	if b < 0:
		m = (-b + c - 1) // c
		return Solve(a, b + m * c, c, n) - m * n
	if a >= c:
		return a // c * (n * (n + 1) // 2) + Solve(a % c, b, c, n)
	m = (a * n + b) // c
	return (n + 1) * m - Solve(c, a - b - 1, a, m)
n = int(input())
C = 1
A = 1
lim = 3000
for i in range(1, lim):
	C *= i
for i in range(1, lim):
	A = A * i + 1
print(Solve(A, 0, C, n))


n = int(input())

def gcd(a, b):
	while a:
		(a, b) = (b % a, a)
	return b
frac = [1, 2]
for i in range(2, 2001):
	frac += [1, 1, 2 * i]
den = 1
num = 0
de = 0
nu = 1
for i in range(len(frac)):
	(num, den, nu, de) = (frac[i] * num + nu, frac[i] * den + de, num, den)
	if den > n:
		break
s = n * (n + 1)
t = gcd(num, den)
num = num // t
den = den // t
z = 1
while den > 0 and n > 0:
	t = num // den
	s += z * t * n * (n + 1) // 2
	num -= den * t
	t = n // den
	s += z * num * t * (n + 1) - z * t * (num * den * t + num + den - 1) // 2
	n -= den * t
	t = n * num // den
	s += z * t * n
	n = t
	temp = num
	num = den
	den = temp
	z *= -1
print(s)


def range_prod(lo, hi):
	if lo + 1 < hi:
		mid = (hi + lo) // 2
		return range_prod(lo, mid) * range_prod(mid + 1, hi)
	if lo == hi:
		return lo
	return lo * hi

def treefactorial(n):
	if n < 2:
		return 1
	return range_prod(1, n)

def puy(x):
	t = 1
	res = 1
	while x > 0:
		t = t * x
		res = res + t
		x = x - 1
	return res

def gcd(x, y):
	while y != 0:
		temp = x
		x = y
		y = temp % y
	return x

def euler(n, p, q):
	t = gcd(p, q)
	p = p // t
	q = q // t
	s = 0
	z = 1
	while q > 0 and n > 0:
		t = p // q
		df = z * t * n * (n + 1) // 2
		s = s + df
		df = q * t
		p = p - df
		t = n // q
		df = z * p * t * (n + 1) - z * t * (p * q * t + p + q - 1) // 2
		s = s + df
		df = q * t
		n = n - df
		t = n * p // q
		df = z * t * n
		s = s + df
		n = t
		temp = p
		p = q
		q = temp
		z = -z
	return s
n = int(input())
print(euler(n, puy(3000), treefactorial(3000)))


import sys
sys.setrecursionlimit(1000000000)

def solve(A, B, C, n):
	if A == 0:
		return (n + 1) * (B // C)
	if A >= C:
		return solve(A % C, B, C, n) + n * (n + 1) // 2 * (A // C)
	if B >= C:
		return solve(A, B % C, C, n) + (n + 1) * (B // C)
	m = (A * n + B) // C
	return n * m - solve(C, C - B - 1, A, m - 1)
n = int(input())
C = 1
A = 1
lim = 3000
for i in range(1, lim):
	C *= i
for i in range(1, lim):
	A = A * i + 1
print(solve(A, 0, C, n))


def approxi():
	num = 1
	den = 1
	fact = 1
	for x in range(1, 3000):
		num = num * x + 1
		den = fact
		fact *= x + 1
	return (num, den)
n = int(input())
(p, q) = approxi()
p = p // 20
q = q // 20
s = 0
z = 1
while q > 0 and n > 0:
	t = p // q
	s = s + z * t * n * (n + 1) // 2
	p = p - q * t
	t = n // q
	s = s + z * p * t * (n + 1) - z * t * (p * q * t + p + q - 1) // 2
	n = n - q * t
	t = n * p // q
	s = s + z * t * n
	n = t
	(p, q) = (q, p)
	z = -z
print(s)


def approx():
	n0 = 2
	d0 = 1
	n1 = 3
	d1 = 1
	j = 0
	k = 0
	for i in range(5000):
		if i % 3 == 0:
			j = k + 2
			k = j
		else:
			j = 1
		n = j * n1 + n0
		d = j * d1 + d0
		(n1, n0) = (n, n1)
		(d1, d0) = (d, d1)
	return (n1, d1)
n = int(input())
(p, q) = approx()
s = 0
z = 1
while q > 0 and n > 0:
	t = p // q
	s = s + z * t * n * (n + 1) // 2
	p = p - q * t
	t = n // q
	s = s + z * p * t * (n + 1) - z * t * (p * q * t + p + q - 1) // 2
	n = n - q * t
	t = n * p // q
	s = s + z * t * n
	n = t
	(p, q) = (q, p)
	z = -z
print(s)


n = int(input())
num = 1
den = 1
for i in range(1, 4001):
	num = num * i + 1
	den *= i
flag = 1
ans = 0
while n > 0:
	if num >= 2 * den:
		k = (num - den) // den
		ans += flag * k * n * (n + 1) // 2
		num -= k * den
	else:
		alpn = num * n // den
		ans += flag * (alpn * (alpn + 1) // 2)
		flag *= -1
		den = num - den
		n = alpn - n
print(ans)


import math
u = 2682
kf = 1
uf = math.factorial(u)
num = uf
den = uf
for k in range(1, u):
	kf *= k
	num += uf // kf
ans = 0
sign = 1
m = 0
n = int(input())
while n:
	m = num // den - 1
	ans += m * sign * (n * (n + 1) >> 1)
	num -= m * den
	n2 = n
	n = n * num // den
	ans += sign * (n * (n + 1) >> 1)
	sign *= -1
	den = num - den
	n = n - n2
print(ans)


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

def fact(x):
	res = 1
	for i in range(2, x + 1):
		res *= i
	return res

def nom(x):
	(t, res) = (1, 1)
	while x > 0:
		t *= x
		res += t
		x -= 1
	return res
from sys import stdin, stdout
B = stdin.readline().rstrip()
B = int(B)
C = int(0)
P = nom(3000)
Q = fact(3000)
P = int(P)
Q = int(Q)
T = gcd(P, Q)
P = P // T
Q = Q // T
Z = 1
while Q > 0 and B > 0:
	T = P // Q
	T = int(T)
	C = C + Z * T * B * (B + 1) // 2
	P = P - Q * T
	T = B // Q
	T = int(T)
	C = C + Z * P * T * (B + 1) - Z * T * (P * Q * T + Q + P - 1) // 2
	B = B - Q * T
	T = B * P // Q
	T = int(T)
	C = C + Z * T * B
	B = T
	temp = Q
	Q = P
	P = temp
	Z = -Z
stdout.write(str(int(C)))


from decimal import *
from fractions import *
a = [2, 1, 2, 1, 1, 4, 1, 1, 6]
hn = []
kn = []
getcontext().prec = 10

def gen():
	for n in range(9, 10005, 1):
		x = 2 * a[n - 3] - a[n - 6]
		a.append(x)
		hn.append(0)
		kn.append(0)
	hn[8001] = a[8001]
	kn[8001] = 1
	for i in range(8000, -1, -1):
		hn[i] = hn[i + 1] * a[i] + kn[i + 1]
		kn[i] = hn[i + 1]

def rec_again(n):
	sol = 0
	cnt = 0
	while n > 0:
		ext = 0
		cur = 0
		g = a[cnt]
		ext = n * (n + 1) * g // 2
		hn[cnt] -= kn[cnt] * a[cnt]
		n1 = n * hn[cnt] // kn[cnt]
		if cnt == 0:
			ext = ext // 2
		cur = ext + (n + n1) * (n + n1 + 1) // 2
		if cnt % 2:
			sol = sol - cur
		else:
			sol = sol + cur
		n = n1
		cnt += 1
	return int(sol)
gen()
num = int(input())
print(rec_again(num))


import sys
n0 = int(input())

def eMake(n):
	a = 0
	b = 1
	while n > 2:
		i = b * n + a
		(a, b) = (i + b, i + i + b)
		n -= 2
	(a, b) = (b, 2 * b + a)
	(a, b) = (b, b + a)
	a = a + 2 * b
	return [a, b]

def anMy(a0, b0, n0):
	re = 0
	si = 1
	a = a0
	b = b0
	n = n0
	while n > 0:
		k = a // b
		if k > 1:
			re = re + (k - 1) * n * (n + 1) // 2 * si
			a = a - b * (k - 1)
		else:
			m = (a - b) * n // b
			re = re + (n + m) * (n + m + 1) // 2 * si
			b = a - b
			si = -si
			n = m
	return re
e = eMake(2480)
print(anMy(e[0], e[1], n0))


import math
b = 1
a = 1
for i in range(1, 3500):
	a = a * i + 1
	b *= i
n = int(input())
ans = 0
sign = True
while n >= 1:
	if n <= 1:
		if sign:
			ans += n * a // b
		else:
			ans -= n * a // b
		break
	if a >= 2 * b:
		c = a // b - 1
		if sign:
			ans += c * n * (n + 1) // 2
		else:
			ans -= c * n * (n + 1) // 2
		a -= c * b
	m = (a - b) * n // b
	assert b < a and a < 2 * b
	if sign:
		ans += (n + m) * (n + m + 1) // 2
	else:
		ans -= (n + m) * (n + m + 1) // 2
	b = a - b
	n = m
	sign = not sign
print(ans)


import math
from decimal import *

def work(n, a, c):
	res = 0
	rev = False
	while True:
		if n < 5000:
			for i in range(1, n + 1):
				tmp = i * a // c
				if rev == False:
					res += tmp
				else:
					res -= tmp
			break
		if a >= c:
			tmp = n * (n + 1) // 2 * (a // c)
			if rev == False:
				res += tmp
			else:
				res -= tmp
			a %= c
		m = n * a // c
		tmp = n * m
		if rev == False:
			res += tmp
		else:
			res -= tmp
		if a > 0:
			n = m
			t = a
			a = c
			c = t
			rev = not rev
		else:
			break
	return res
n = int(input())
w = str(n).__len__() * 2 + 5
getcontext().prec = w + 5
c = int('1' + '0' * w)
e = Decimal(0)
fac = Decimal(1)
for i in range(1, 2700):
	e += fac
	fac /= i
a = int(e * c)
print(work(n, a, c))


from decimal import *
import math

def calc(a, b, n):
	ans = 0
	flag = 1
	while a != 0 and b != 0:
		sum = a // b * n * (n + 1) // 2
		a %= b
		if a == 0 or b == 0:
			if flag == 1:
				ans += sum
			else:
				ans -= sum
			break
		else:
			t = a * n // b
			if flag == 1:
				ans += sum + n * t + n // b
			else:
				ans -= sum + n * t + n // b
			n = t
			t = b
			b = a
			a = t
		flag = -flag
	return ans
getcontext().prec = 8010
e = Decimal(0)
i = 0
fact = Decimal(1)
while i <= 2700:
	e += fact
	i += 1
	fact = fact / i
pw = 1
for i in range(8005):
	e = e * 10
	pw = pw * 10
e = int(e)
n = int(input())
print(calc(e, pw, n))


def e(count):
	(h1, h2) = [2, 1]
	(k1, k2) = [1, 0]
	arr = [1, 0, 1]
	for i in range(1, count, 3):
		arr[1] += 2
		for a in arr:
			(h1, h2) = [a * h1 + h2, h1]
			(k1, k2) = [a * k1 + k2, k1]
	return (h1, k1)

def S(alfa, n):
	(p, q) = alfa
	result = 0
	sign = 1
	while 1:
		if p == q:
			result += sign * n * (n + 1) // 2
			return result
		if n <= 100:
			for k in range(1, n + 1):
				result += sign * (p * k // q)
			return result
		if p > 2 * q:
			count = p // q - 1
			result += sign * (n * (n + 1) // 2) * count
			(p, q) = (p - q * count, q)
		else:
			n1 = n * (p - q) // q
			sumofn = n + n1
			result += sign * (sumofn * (sumofn + 1) // 2)
			(p, q) = (p, p - q)
			n = n1
			sign *= -1
n = int(input())
print(S(e(4000), n))


atulag_cf = []
atulag_cf.append(2)
for i in range(1, 1334):
	atulag_cf.append(1)
	atulag_cf.append(2 * i)
	atulag_cf.append(1)
(p, q) = ([], [])
p.append(atulag_cf[len(atulag_cf) - 1])
q.append(1)
for i in range(1, len(atulag_cf)):
	j = len(atulag_cf) - 1 - i
	(pj, qj) = (p[0] * atulag_cf[j] + q[0], p[0])
	p.insert(0, pj)
	q.insert(0, qj)
n = int(input())
recToLoop = []
tp = []
sum = 0
while n != 0:
	if p[0] > 2 * q[0]:
		m = atulag_cf[0] - 1
		atulag_cf[0] = 1
		p[0] = q[1] + p[1]
		recToLoop.append(m * n * (n + 1))
		tp.append(1)
	else:
		fparam1n = p[0] * n // q[0]
		n = (p[0] - q[0]) * n // q[0]
		atulag_cf.pop(0)
		p.pop(0)
		q.pop(0)
		atulag_cf[0] = atulag_cf[0] + 1
		p[0] = p[0] + q[0]
		recToLoop.append(fparam1n * (fparam1n + 1))
		tp.append(2)
while tp:
	if tp.pop() == 1:
		sum = recToLoop.pop() + sum
	else:
		sum = recToLoop.pop() - sum
print(sum // 2)


def epsilon(nom, dem, n):
	i = 1
	s = 0
	while n != 0:
		t = 0
		t += (nom // dem - 1) * n * (n + 1) // 2
		nom %= dem
		np = nom * n // dem
		t += (n + np) * (n + np + 1) // 2
		if i == 1:
			s += t
		else:
			s -= t
		i ^= 1
		n = np
		t = nom
		nom += dem
		dem = t
	return s
nom = 1
dem = 1
count = 2675
i = 1
while i <= count:
	nom = nom * i + 1
	dem *= i
	i += 1
n = int(input())
s = epsilon(nom, dem, n)
print(s)


import math
import decimal
import time

def epsilon(nom, dem, n):
	i = 1
	s = 0
	while n != 0:
		t = 0
		t += (nom // dem - 1) * n * (n + 1) // 2
		nom %= dem
		np = nom * n // dem
		t += (n + np) * (n + np + 1) // 2
		if i == 1:
			s += t
		else:
			s -= t
		i ^= 1
		n = np
		t = nom
		nom += dem
		dem = t
	return s
nom = 1
dem = 1
count = 2675
i = 1
while i <= count:
	nom = nom * i + 1
	dem *= i
	i += 1
n = int(input())
s = epsilon(nom, dem, n)
print(s)


import math as ma
Q = list()
y = Q.append
y(2)
y(1)
for x in range(1, 1400):
	y(x * 2)
	y(1)
	y(1)
p = []
q = []
p.append(Q[len(Q) - 1])
q.append(1)
for i in range(1, len(Q)):
	j = len(Q) - 1 - i
	pj = p[0] * Q[j] + q[0]
	qj = p[0]
	p.insert(0, pj)
	q.insert(0, qj)

def S(n):
	o = 0
	sign = 1
	while n > 0:
		if p[0] > 2 * q[0]:
			m = Q[0] - 1
			Q[0] = 1
			p[0] = q[1] + p[1]
			o = o + sign * m * n * (n + 1)
		else:
			m = p[0] * n // q[0]
			o = o + sign * (m + 1) * m
			n = (p[0] - q[0]) * n // q[0]
			Q.pop(0)
			p.pop(0)
			q.pop(0)
			Q[0] = Q[0] + 1
			p[0] = p[0] + q[0]
			sign = -sign
	return o
n = int(input())
ans = S(n)
print(ans // 2)


import sys
sys.setrecursionlimit(20000)

def fn(num, den, p):
	if p == 0:
		return 0
	elif p == 1 or num == den:
		return 1
	else:
		t = num // (num - den) - 1
		p1 = p * (num - den) // den
		return num * p // den * (num * p // den + 1) // 2 - t * (p1 * (p1 + 1) // 2) - fn(num + t * (den - num), num - den, p1)

def contfrac_to_frac(seq):
	(num, den) = (1, 0)
	for u in reversed(seq):
		(num, den) = (den + num * u, num)
	return (num - den, den)

def e_cont_frac(n):
	seq = [2 * (i + 1) // 3 if i % 3 == 2 else 1 for i in range(n)]
	seq[0] += 1
	return seq
p = int(input())
n = 4000
seq = e_cont_frac(n)
(num, den) = contfrac_to_frac(seq)
ans = fn(num, den, p)
print(ans + p * (p + 1) // 2)


from decimal import *
import math
import sys
x = 1
y = 0
z = 1
i = 0
n = int(input())
while z < n:
	i = i + 1
	x = y + z
	y = 2 * i * x + z
	z = x + y
st = 0
if x >= n:
	a = x
	st = 1
elif y >= n:
	a = y
	st = 2
else:
	a = z
	st = 3
j = 0
x = 1
y = 1
z = 2
while j < i:
	j = j + 1
	x = y + z
	y = 2 * j * x + z
	z = x + y
if st == 1:
	b = x
elif st == 2:
	b = y
else:
	b = z
if n == 1:
	print(2)
	sys.exit()
ans = 0
x = 1
i = 0
while n > 0:
	i = i + 1
	y = b // a
	if y > 1:
		y = y - 1
		if x > 0:
			ans = ans + y * n * (n + 1) // 2
		else:
			ans = ans - y * n * (n + 1) // 2
		b = b - a * y
	else:
		y = b * n // a
		if x > 0:
			ans = ans + y * (y + 1) // 2
		else:
			ans = ans - y * (y + 1) // 2
		x = x * -1
		a = b - a
		n = y - n
print(math.floor(ans))


n = int(input())
dena = 1
numa = 1
for i in range(2700, 0, -1):
	dena *= i
	numa += dena
y = 0
k = 1
cnt2 = 2
tempn = 0
while n > 0:
	if cnt2 == 0:
		tempn += 2
		diff = tempn
		cnt2 = 2
	else:
		diff = 1
		cnt2 -= 1
	numa = numa - diff * dena
	numa = numa - dena
	n2 = numa * n // dena
	y += k * (diff * n * (n + 1) + (n + n2) * (n + n2 + 1))
	k = -k
	n = n2
	(numa, dena) = (dena, numa)
	numa += dena
print(y // 2)


from fractions import gcd
import math

def e_frac():
	(num, den) = (2, 1)
	k = 2
	while k < 4100:
		num = num * k + 1
		den *= k
		k += 1
	g = gcd(num, den)
	return (num // g, den // g)

def ES(n):
	res = 0
	flip = False
	(a_num, a_den) = e_frac()
	while True:
		if a_num >= 2 * a_den:
			sub = a_num // a_den - 1
			a_num = a_den + a_num % a_den
			if a_num == a_den:
				res += (sub + 1) * (n * (n + 1) // 2) * (-1 if flip else 1)
				break
			else:
				res += sub * (n * (n + 1) // 2) * (-1 if flip else 1)
		nplum = (a_num - a_den) * n // a_den
		plus = n + nplum
		if plus == 0:
			break
		res += plus * (plus + 1) // 2 * (-1 if flip else 1)
		a_den = a_num - a_den
		flip = not flip
		n = nplum
	return res
N = int(input())
print('%d' % ES(N))


def A(n):
	if n % 3 == 0:
		return 2 * (n // 3)
	if n == 1:
		return 2
	return 1
num = 1
den = 0
for i in range(5000, 0, -1):
	(num, den) = (A(i) * num + den, num)
n = int(input())
ans = 0
it = 1
while n:
	if num > den + den:
		x = (num - den) // den
		num -= x * den
		if it == 0:
			ans -= x * n * (n + 1) // 2
		else:
			ans += x * n * (n + 1) // 2
	else:
		nn = (num - den) * n // den
		if it == 0:
			ans -= (n + nn) * (n + nn + 1) // 2
		else:
			ans += (n + nn) * (n + nn + 1) // 2
		n = nn
		den = num - den
		it ^= 1
print(ans)


import math
import fractions
n = int(input())
a = 1
b = math.factorial(3000)
m = 1
for i in range(3000, 0, -1):
	m *= i
	a += m
g = fractions.gcd(a, b)
a //= g
b //= g
ans = 0
m = 1
while b and n:
	ans += a // b * n * (n + 1) // 2 * m
	a %= b
	k = n // b
	ans += (n * a * 2 - a * k * b + a - (b - 1)) * k // 2 * m
	n %= b
	k = n * a // b
	ans += k * n * m
	(n, a, b) = (k, b, a)
	m *= -1
print(ans)


w = 9000

def getE():
	tmp = 10 ** w
	e = tmp
	gt = 1
	while tmp >= gt:
		tmp //= gt
		e += tmp
		gt += 1
	return e

def f(a, b, c, n):
	sign = 1
	ans = 0
	while True:
		if a >= c:
			ans += sign * (a // c) * n * (n + 1) // 2
			a %= c
			continue
		if b >= c:
			ans += sign * (b // c) * (n + 1)
			b %= c
			continue
		m = (a * n + b) // c
		if m == 0:
			break
		ans += sign * n * m
		sign = -sign
		(a, b, c, n) = (c, c - b - 1, a, m - 1)
	return ans
n = int(input().rstrip())
res = f(getE(), 0, int(10 ** w), n)
print(res)


MAXN = 10000
a = [2, 1, 2, 1, 1]
p = [2, 3, 8, 11, 19]
q = [1, 1, 3, 4, 7]
j = 0
c = -1
n = int(input())
suff = 0
res = 0
for i in range(5, MAXN):
	if a[i - 1] == 1 and a[i - 2] == 1:
		a.append(a[i - 3] + 2)
	else:
		a.append(1)
	p.append(a[i] * p[i - 1] + p[i - 2])
	q.append(a[i] * q[i - 1] + q[i - 2])
	if q[i] > n:
		break
for i in range(0, MAXN):
	if q[i] > n:
		break
	j = i
	c = -c
for i in range(j, 0, -1):
	z = n // q[i]
	if z > 0:
		n -= z * q[i]
		res += z * (z * p[i] * q[i] - q[i] + p[i] + c) // 2
		res += z * q[i] * suff
		suff += z * p[i]
	c = -c
print(res)


def floor_sum(p, q, n):
	sgn = 1
	res = 0
	while n > 0:
		if n >= q:
			t = n // q
			res += t * (q - 1) * (p - 1) // 2 * sgn
			res += p * (n + 1) * t * sgn
			res -= q * t * (t + 1) // 2 * sgn
			n -= q * t
		if p > q:
			t = p // q
			res += t * n * (n + 1) // 2 * sgn
			p -= q * t
		if n == 0:
			return res
		if n == 1:
			return res + p // q * sgn
		m = p * n // q
		res += sgn * n * m
		sgn = -sgn
		n = m
		m = p
		p = q
		q = m
	return res

def main():
	n = int(input())
	k = 1
	p = 2
	q = 1
	while q < n:
		k = k + 1
		q *= k
		p = p * k + 1
	for i in range(1250):
		k = k + 1
		q *= k
		p = p * k + 1
	for d in range(2, k):
		while p % d == 0 and q % d == 0:
			p = p // d
			q = q // d
	res = floor_sum(p, q, n)
	print(res)
main()


import sys
fracs = []

def contfrac_to_frac(seq):
	(num, den) = (1, 0)
	for u in reversed(seq):
		(num, den) = (den + num * u, num)
		fracs.append((num, den))

def e_cont_frac(n):
	seq = [2 * (i + 1) // 3 if i % 3 == 2 else 1 for i in range(n)]
	seq[0] += 1
	return seq
seq = e_cont_frac(4200)
contfrac_to_frac(seq)
fracs.reverse()

def getans(num, den, n):
	if n == 0:
		return 0
	if n == 1:
		return num // den
	if num // den >= 2:
		return (num // den - 1) * n * (n + 1) // 2 + getans(den + num % den, den, n)
	nt = num % den * n // den
	return (n + nt) * (n + nt + 1) // 2 - getans(num, num - den, nt)
(num, den) = fracs[0]
n = int(input())
sys.setrecursionlimit(10000)
print(getans(num, den, n))


nr = 3
nr1 = 2
dr = 1
dr1 = 1
ans = 0
t = 3
n = int(input())
if n == 1:
	nr = 2
while dr < n:
	if t % 3 == 0:
		a = nr * (t // 3) * 2 + nr1
		nr1 = nr
		nr = a
		a = dr * (t // 3) * 2 + dr1
		dr1 = dr
		dr = a
	else:
		a = nr + nr1
		nr1 = nr
		nr = a
		a = dr + dr1
		dr1 = dr
		dr = a
	t = t + 1
t = 0
while n > 0:
	t = t + 1
	n1 = nr // dr
	a = 0
	if n1 > 1:
		a = int(n * (n + 1) // 2)
		a = int(a * (n1 - 1))
	nr = nr % dr + dr
	n1 = (nr - dr) * n // dr
	dr = nr - dr
	if t % 2 == 1:
		ans = ans + a + int((n + n1) * (n + n1 + 1) // 2)
	else:
		ans = ans - a - int((n + n1) * (n + n1 + 1) // 2)
	n = n1
print(ans)


from math import *
from fractions import *

def compBF(n):
	S = 0
	for i in range(n + 1):
		S += floor(e * i)
	return S

def build_e(bnd=10 ** 4000):
	(n0, d0, n1, d1) = (2, 1, 3, 1)
	r = [(n0, d0), (n1, d1)]
	i = 3
	f = 2
	while d1 <= bnd:
		f = 1
		if i % 3 == 0:
			f = i // 3 * 2
		i += 1
		n2 = f * n1 + n0
		d2 = f * d1 + d0
		(n1, n0) = (n2, n1)
		(d1, d0) = (d2, d1)
		r.append((n1, d1))
	return r

def comp(N):
	q = build_e(N)
	S = 0
	f = q.pop()
	f = Fraction(f[0], f[1])
	while N > 0:
		g = f.limit_denominator(N)
		(n, d) = (g.numerator, g.denominator)
		(a, r) = (N // d, N % d)
		S += ((a * n - 1) * (a * d - 1) - (a - 1)) // 2 + a * (r + 1) * n - 1
		if g < f:
			S += a
		(N, f) = (r, g)
	return S

def comp2(N):
	q = build_e(N)
	S = 0
	f = q.pop()
	f = Fraction(f[0], f[1])
	while N > 0:
		g = q.pop()
		while g[1] > N:
			g = q.pop()
		(n, d) = g
		g = Fraction(n, d)
		(a, r) = (N // d, N % d)
		S += ((a * n - 1) * (a * d - 1) - (a - 1)) // 2 + a * (r + 1) * n - 1
		if g < f:
			S += a
		(N, f) = (r, g)
	return S
N = int(input())
print(comp2(N))
exit(0)
for i in range(10000):
	r1 = comp(i)
	r2 = comp2(i)
	print('res: ', i, r1, r2)
	assert r1 == r2


def S(a, n):
	ans = 0
	sign = 1
	while n > 0:
		if a[-1] >= 2:
			if sign == 1:
				ans += (a[-1] - 1) * n * (n + 1)
			else:
				ans -= (a[-1] - 1) * n * (n + 1)
			a[-1] = 1
		else:
			p = 1
			q = 0
			a[-1] = a[-1] - 1
			for i in a:
				(p, q) = (q + i * p, p)
			nPrim = p * n // q
			if sign == 1:
				x = n + nPrim
				ans += x * (x + 1)
			else:
				x = n + nPrim
				ans -= x * (x + 1)
			a.pop()
			a[-1] = a[-1] + 1
			n = nPrim
			sign *= -1
	return ans // 2

def main():
	e = [2 * (i + 1) // 3 if i % 3 == 2 else 1 for i in range(4020)]
	e[0] += 1
	e.reverse()
	n = int(input())
	print(S(e, n))
main()


import math

def e_cont_frac(n):
	a = [2 * (i + 1) // 3 if i % 3 == 2 else 1 for i in range(n)]
	a[0] += 1
	a.reverse()
	return a

def rec(a, n):
	res = 0
	sign = 1
	while n > 0:
		if a[-1] >= 2:
			res += sign * (a[-1] - 1) * n * (n + 1) // 2
			a[-1] = 1
		x = 1
		y = 0
		for i in a:
			aux = y
			y = x
			x = aux + i * x
		n_prim = n * (x - y) // y
		res += sign * (n + n_prim) * (n + n_prim + 1) // 2
		sign = -sign
		n = n_prim
		a.pop()
		a[-1] = a[-1] + 1
	return res

def main():
	n = int(input())
	print(int(rec(e_cont_frac(4010), n)))
main()


from decimal import Decimal, getcontext
import math
o = 9000
getcontext().prec = o

def get2(x):
	return x * (x + 1) // 2

def ceil(x):
	ans = x.to_integral_exact()
	if ans > x:
		ans = ans - 1
	return int(ans)

def getans(n, aa, bb):
	s = 1
	ans = 0
	while n >= 2:
		xx = aa // bb
		ans += s * (xx - 1) * get2(n)
		aa -= xx * bb
		n1 = aa * n // bb
		ans += s * get2(n + n1)
		s *= -1
		n = n1
		aa = aa + bb
		bb = aa - bb
	xx = aa // bb
	return ans + n * xx * s
e = Decimal(0)
f = Decimal(1)
n = Decimal(1)
while n < 4500:
	e += f
	f /= n
	n += Decimal(1)
z = 1
h = 0
while h < o:
	h += 1
	z *= 10
aa = ceil(e * Decimal(z))
bb = z
n = int(input())
a = getans(n, aa, bb)
print(a)


import sys
sys.setrecursionlimit(5000)
from math import e

def E(n):
	return int(n * e)

def cf(n):
	if n == 0:
		return 0
	elif n % 3 == 1:
		return 2 * (n // 3 + 1)
	return 1
Size = [1, 1]
Sums = [3, 2]
for i in range(5000):
	d = cf(i)
	Size.append(d * Size[-1] + Size[-2])
	Sums.append(d * Sums[-1] + Sums[-2])
memo = {}

def _ST(k, n):
	if k <= 3:
		return sum((E(i) - 2 for i in range(1, n + 1)))
	if (k, n) in memo:
		return memo[k, n]
	assert Size[k] == Size[k - 1] * cf(k - 2) + Size[k - 2]
	assert n <= Size[k]
	d = cf(k - 2)
	(x, y) = (n // Size[k - 1], n % Size[k - 1])
	assert x <= d
	res = (x - 1) * x // 2 * Sums[k - 1] * Size[k - 1] + y * x * Sums[k - 1] + x * _ST(k - 1, Size[k - 1])
	if x < d:
		res += _ST(k - 1, y)
	else:
		res += _ST(k - 2, y)
	memo[k, n] = res
	return res

def ST(n):
	k = 0
	while Size[k] < n:
		k += 1
	return 2 * n + _ST(k, n)
print(ST(int(input())))


z = 1550
(p, q) = (4 * z + 2, 1)
for i in range(1, z):
	j = z - i
	(p, q) = (q, p)
	p += 4 * j * q + 2 * q
q += p
p += p
p += q
x = int(input())
ans = 0
flag = 1
while x > 0:
	if p >= q + q:
		sub = (p - q) // q
		ans += flag * sub * x * (x + 1) // 2
		p -= q * sub
	y = x * p // q
	ans += flag * y * (y + 1) // 2
	x = y - x
	q = p - q
	flag *= -1
print(ans)


def S(n, p, q):
	s = 0
	z = 1
	while q > 0 and n > 0:
		t = p // q
		s = s + z * t * n * (n + 1) // 2
		p = p - q * t
		t = n // q
		s = s + z * p * t * (n + 1) - z * t * (p * q * t + p + q - 1) // 2
		n = n - q * t
		t = n * p // q
		s = s + z * t * n
		n = t
		tem = p
		p = q
		q = tem
		z = -z
	return s
(N0, N) = (1, 2)
LIM = 4000 + 2
for i in range(3, LIM):
	m = 1
	if (i - 1) % 3 == 0:
		m = 2 * (i - 1) // 3
	naya = N0 + N * m
	(N0, N) = (N, naya)
(D0, D) = (1, 1)
for i in range(3, LIM - 1):
	m = 1
	if i % 3 == 0:
		m = 2 * i // 3
	naya = D0 + D * m
	(D0, D) = (D, naya)
x = input()
x = int(x)
ans = S(x, N, D)
print(ans)


import math
p = [0 for i in range(4000 + 1)]
q = [0 for i in range(4000 + 1)]
p[0] = 2
q[0] = 1
p[1] = 3
q[1] = 1
p[2] = 8
q[2] = 3
for n in range(3, 4001):
	a = 0
	if n % 3 == 1 or n % 3 == 0:
		a = 1
	else:
		a = (n + 1) // 3 * 2
	p[n] = a * p[n - 1] + p[n - 2]
	q[n] = a * q[n - 1] + q[n - 2]
up = p[4000]
down = q[4000]
dic = {}

def findout(p, q, n):
	K = p // q
	temp = n * (n + 1) // 2 * K
	p = p - q * K
	M = n * p // q
	if M == 0:
		return temp
	if (p, q, n) in dic:
		return dic[p, q, n]
	KK = q * (M + 1) // p
	LLL = n * M - findout(q, p, M) + temp
	dic[p, q, n] = LLL
	return LLL
p = up
q = down
n = int(input())
seq = [(p, q, n)]
while 1:
	K = p // q
	p = p - q * K
	M = n * p // q
	(p, q) = (q, p)
	n = M
	if M != 0:
		seq += [(p, q, n)]
	else:
		break
seq = seq[::-1]
temp = 0
for i in range(len(seq)):
	(p, q, n) = seq[i]
	temp = findout(p, q, n)
print(temp)


def gen_e_convergents():
	(h0, h1) = (2, 3)
	(k0, k1) = (1, 1)
	yield (h1, k1)
	n = 2
	while True:
		(h0, h1) = (h1, n * h1 + h0)
		(k0, k1) = (k1, n * k1 + k0)
		yield (h1, k1)
		for i in range(2):
			(h0, h1) = (h1, h1 + h0)
			(k0, k1) = (k1, k1 + k0)
			yield (h1, k1)
		n += 2

def fsum(n, p, q):
	s = 0
	z = 1
	while q > 0 and n > 0:
		t = p // q
		s += z * t * n * (n + 1) // 2
		p -= q * t
		t = n // q
		s += z * p * t * (n + 1) - z * t * (p * q * t + p + q - 1) // 2
		n -= q * t
		t = n * p // q
		s += z * t * n
		n = t
		(p, q) = (q, p)
		z = -z
	return s

def sol1(n):
	if n == 1:
		return 2
	for (h, k) in gen_e_convergents():
		if k >= n:
			break
	return fsum(n, h, k)
n = int(input())
print(sol1(n))


def calc_e(N0):
	sd = '1'
	for n in range(0, N0 + 11):
		sd += '0'
	d = int(sd)
	e = 0
	f = 2
	n = 3
	while True:
		olde = e
		e += d // f
		if f > d:
			break
		f *= n
		n += 1
	return (e, d)
P = input()
ln = len(P)
N = int(P)
R = N * (N + 1)
if ln <= 101:
	(p, q) = calc_e(202)
else:
	(p, q) = calc_e(8004)
s = 0
n = N
while q > 0 and n > 0:
	t = p // q
	if t != 0:
		s = s + t * n * (n + 1) // 2
		p = p - q * t
	t = n // q
	if t != 0:
		s = s + p * t * (n + 1) - t * (p * q * t + p + q - 1) // 2
		n = n - q * t
	t = n * p // q
	s = s + t * n
	n = t
	(p, q) = (q, p)
	if q == 0 and n == 0:
		break
	t = p // q
	if t != 0:
		s = s - t * n * (n + 1) // 2
		p = p - q * t
	t = n // q
	if t != 0:
		s = s - p * t * (n + 1) + t * (p * q * t + p + q - 1) // 2
		n = n - q * t
	t = n * p // q
	s = s - t * n
	n = t
	(p, q) = (q, p)
print(R + s)


Umi = 2500
p = 1
q = 1
for i in range(Umi, 0, -2):
	(p, q) = (q, p + i * q)
	(p, q) = (q, p + q)
	(p, q) = (q, p + q)
(p, q) = (q, p)
p += q
n = int(input())
n += 1
ans = 0
a = 0
b = p
m = q
while True:
	if b == 0:
		ans += n * (a // m)
		break
	if a >= m:
		ans += n * (a // m)
		a %= m
	elif b >= m:
		ans += (n - 1) * n // 2 * (b // m)
		b %= m
	else:
		(n, a, b, m) = ((a + b * n) // m, (a + b * n) % m, m, b)
print(ans)


import sys

def count_lattice_points(x, numer, denom):
	if x == 0 or numer == 0:
		return 0
	if x >= denom:
		(q, r) = divmod(x, denom)
		ret = q * (q * numer * denom - denom + numer + 1) >> 1
		ret += r * q * numer
		ret += count_lattice_points(r, numer, denom)
		return ret
	elif numer >= denom:
		(q, r) = divmod(numer, denom)
		return (x * (x + 1) * q >> 1) + count_lattice_points(x, r, denom)
	else:
		q = numer * x // denom
		return x * q - count_lattice_points(q, denom, numer)

def solve():
	sys.setrecursionlimit(20000)
	nu = 0
	de = 1
	K = 4000
	for k in range(K, 0, -1):
		v = k // 3 * 2 if k % 3 == 0 else 1
		(nu, de) = (de, nu + v * de)
	(de, nu) = (nu, de)
	nu += de
	input = sys.stdin.readline
	N = int(input())
	print(count_lattice_points(N, nu, de))
solve()