시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB48272352.273%

문제

계란으로 돈을 벌면? 에그머니나!

"계란을 떨어뜨리면?" 문제에서 계란을 떨어뜨린 재우는 삽시간에 SNS에서 유명해지며, 계란 떨어뜨리기를 통해 돈을 벌기로 했다. 재우는 $K$일에 걸쳐 각각의 날마다 계란을 준비해 쇼를 보여주기로 했다. 재우는 $K$일 동안 꾸준히 기대감을 주기 위해 $i$번째 날에 $i$개의 계란을 준비해 떨어뜨리기로 했다. 또, 하루에 너무 많이 떨어뜨리면 팔이 아프므로 하루에 최대 $K$번 떨어뜨리기로 했다. 즉, 앞의 문제에서 $E$의 정의를 가져오면, 재우가 $i$번째 날에 검증할 수 있는 가장 높은 층은 $E(i, K)$이다. 재우가 $K$일에 걸쳐 계란 떨어뜨리기를 통해 각각의 날마다 검증할 수 있는 가장 높은 층을 검증할 때, 각각의 날마다 검증하는 층수의 합을 구해보자.

즉, $\displaystyle\sum_{i=1}^K E(i, K)$를 구하시오.

입력

첫 번째 줄에 $K$ ($1 \le K \le 10^{18}$)가 주어진다.

출력

첫 번째 줄에 $\displaystyle\sum_{i=1}^K E(i,K)$를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

5

$E(1,2) = 2$, $E(2,2) = 3$이다.

예제 입력 2

4

예제 출력 2

43

$E(1,4) = 4$, $E(2,4) = 10$, $E(3,4) = 14$, $E(4,4) = 15$이다.

노트

이 문제의 제목과 제목에 대한 답은 kidw0124의 아이디어이다.

출처

University > 고려대학교 > 제 2회 고려대학교 MatKor Cup: 2023 Winter J번