계란을 떨어뜨리면?

계란을 떨어뜨리면? 에그드랍!

주영이는 매주 화요일마다 MatKor 건물의 지하 1층에 있는 오락실에 리듬 게임을 하러 간다. 재우는 주영이를 따라 오락실에 가 보았지만, 재우는 게임을 매우 못했기 때문에 금세 싫증을 내고 오락실에서 나왔다. 시간이 남은 재우는 MatKor 건물을 보며 하나의 실험을 생각해냈다. MatKor 건물은 1층부터 시작하여 무한히 많은 층으로 이루어져 있으며 각 층에는 창문이 하나씩 나 있다. 재우는 마트에서 달걀을 사 와 과연 몇 층까지는 달걀을 떨어뜨려도 깨지지 않을까, 몇 층부터는 달걀이 깨질까 실험하려고 한다. 재우는 원하는 층에서 창문으로 달걀을 하나 떨어뜨릴 수 있다. 떨어뜨린 달걀은 깨지거나, 깨지지 않는다. 달걀이 깨지지 않았다면 달걀을 주워 와 다시 쓸 수 있지만, 달걀이 깨졌다면 그 달걀은 다시 쓸 수 없다. 모든 달걀은 층수에 따라서만 깨지는지 깨지지 않는지가 결정되며, 달걀을 몇 번 떨어뜨려도 달걀이 깨지는 층의 위치는 변하지 않는다. 또한 어떤 층에서 달걀을 떨어뜨렸을 때 달걀이 깨졌다면 그보다 높은 층에서는 달걀이 무조건 깨지며, 같은 이유로 어떤 층에서 달걀을 떨어뜨렸을 때 달걀이 깨지지 않았다면 그보다 낮은 층에서는 달걀이 무조건 깨지지 않는다는 사실을 재우는 알고 있다.

재우는 현재 가진 돈으로 $N$개의 달걀만 살 수 있다. 또한 달걀을 너무 많이 떨어뜨리면 건물에서 민원이 들어올 수도 있기 때문에, 재우는 총 $K$번의 시도만 하려고 한다(즉 달걀을 총 $K$번만 떨어뜨린다). $K$번의 시도를 모두 수행했거나, 시도가 남았으나 $N$개의 달걀이 모두 깨져 재우가 가진 달걀이 없다면 재우는 실험을 종료한다. 실험을 종료했을 때, 만약 재우가 모든 층에 대해 해당 층에서 달걀을 떨어뜨렸을 때 달걀이 깨지는지 모두 알고 있다면, 재우는 모든 층을 검증했다고 정의한다. 그렇지 않고 재우가 $P$층 이하의 모든 층에 대해 해당 층에서 달걀을 떨어뜨렸을 때 달걀이 깨지는지 모두 알고 있고, $P+1$층에서 달걀을 떨어뜨렸을 때 달걀이 깨지는지 알 수 없다면, 재우는 $P$층을 검증했다고 정의한다.

예를 들어 첫 시도를 1층에서 해서 달걀이 깨지지 않았고, 두 번째 시도를 3층에서 해서 달걀이 깨졌다고 하자. 이때 2층에서 달걀을 떨어뜨렸을 때 달걀이 깨지는지 알 수 없으므로, 재우는 1층을 검증한 것이다. 다른 방법으로, 첫 시도를 1층에서 해서 달걀이 깨지지 않았고, 두 번째 시도를 2층에서 해서 달걀이 깨졌다고 하면, 재우는 3층 이상의 모든 층에 대해서 달걀을 떨어뜨렸을 때 달걀이 깨진다는 것을 알 수 있기 때문에 재우는 모든 층을 검증한 것이다. 같은 방법으로 했을 때 첫 시도와 두 번째 시도에서 모두 달걀이 깨지지 않았다면 재우는 2층을 검증한 것이다.

재우는 $N$개의 달걀과 $K$번의 시도로 어떠한 경우에도(달걀이 몇 층부터 깨지더라도) 검증할 수 있는 가장 높은 층을 $E(N, K)$라고 부르기로 한 뒤, 이를 직접 구하기 위해 달걀을 떨어뜨리기 시작했다. 재우를 도와 $E(N, K)$를 구해 보자.

첫 번째 줄에 재우가 살 수 있는 달걀의 수 $N$ ($1 \le N \le10^{7}$)과 시도의 수 $K$ ($1 \le K \le 10^{7}$)가 공백을 사이에 두고 주어진다. $N$과 $K$는 정수로 주어진다.

재우가 어떠한 경우에도 모든 층을 검증할 수 있다면, 첫 번째 줄에 $-1$을 출력한다.

그렇지 않다면, 첫 번째 줄에 $E(N, K)$를 $1\\,000\\,000\\,007$로 나눈 나머지를 출력한다.

재우가 $K$번의 시도를 했을 때 달걀이 모두 깨지지 않았다면, 재우는 자신이 달걀을 던진 가장 높은 층보다 위의 층에 대해서는 달걀이 깨지는지 알 수 없다. 이러한 경우에서 재우는 모든 층을 검증할 수는 없다. 따라서 '재우가 어떠한 경우에도 모든 층을 검증할 수 있다'는 불가능하며, 모든 양의 정수 $N$과 $K$에 대해 $E(N, K)$가 존재한다.

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