시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
7 초 (추가 시간 없음) | 1024 MB | 82 | 47 | 39 | 88.636% |
메이플스토리에는 235레벨 이후에 갈 수 있는 에스페라란 지역이 있다. "거울에 비친 빛의 신전"이 사냥 효율이 상당히 좋아서 인기가 많다. 여기서 사냥하는 것을 신전 사냥이라고 한다. 위의 그림은 해당 지역을 그래프로 나타낸 것이다.
2019년에 이 신전 사냥과 관련된 재밌는 떡밥이 있었다. 보통 2명이서 사냥을 하면 몹 리젠 속도가 2명이 사냥하는 속도를 따라잡지 못해서 비효율적인데, 미하일이란 직업의 경우에는 사냥 능력이 좋지 않아서 미하일 2명이서 사냥할 때는 서로 영향을 받지 않고 사냥할 수 있었다고 알려진 것이다.
그래서 미하일 2명이 파티를 짜고 사냥을 하기로 결심했다. 해당 그림에서 파란색 원 2개로 표기된 곳이 미하일 2명의 사냥 시작점으로 총 n초 동안 다음과 같이 사냥을 할 것이다.
이 때, n초 동안 사냥할 수 있는 총 방법 수를 1,000,000,007로 나눈 나머지를 구하시오. 미하일 2명이 각각 위치한 곳이 a, b인 경우와 b, a에 있는 경우는 서로 다른 경우로 취급한다.
첫 번째 줄에 정수 n (1 ≤ n ≤ 1,000,000,000)이 주어진다.
n초 동안 사냥할 수 있는 총 방법 수를 1,000,000,007로 나눈 나머지를 구하시오.
1
5
2
10
1000000000
370281159