시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB216475258533.182%

문제

비요뜨는 지금 강 앞에 서 있다. 강 위에는 징검다리가 놓여 있다.

징검다리는 비요뜨가 있는 방향에서부터 반대 방향까지 차례로 1번, 2번, ..., N번의 번호를 가지고 있다.

비요뜨는 1번 징검다리 위에 올라갔다. 그리고 아래 두 가지 규칙을 지키며 징검다리를 건너려고 한다.

  • 1 ≤ X ≤ N 인 임의의 정수 X에 대해, 현재 있는 징검다리의 번호를 i번이라고 할 때 i+X번 징검다리로 뛸 수 있다.
  • N번째 징검다리를 지나쳐선 안 되고, 정확히 도착해야 한다

비요뜨는 자신의 특기인 코딩을 살리기 위해 노트북을 켰지만, 실수로 노트북을 강에 빠뜨리고 말았다.

비요뜨를 대신해 강을 건너는 경우의 수를 구해 주자!

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 1000)

각 테스트 케이스는 한 줄로 구성되며, 징검다리의 개수를 의미하는 N이 주어진다. (1 ≤ N ≤ 109)

출력

각 테스트 케이스에 대해, 한 줄에 하나씩 규칙을 만족하면서 징검다리를 건너는 경우의 수를 109+7로 나눈 나머지를 출력한다.

예제 입력 1

1
4

예제 출력 1

4

강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다.

출처