준혁이는 1번부터 N번 점이 있는 수직선 상에 좌우로 움직이는 로봇을 만들었다.

준혁이는 자신이 만든 로봇의 성능을 검사하기 위해 로봇을 이동시킬 것이다. 구체적으로, 하나의 움직임은 어느 점에서부터 시작해 다른 점으로의 이동을 의미한다.

하지만 로봇이 예를 들어 1->4로 가고, 4->6으로 간다면 준혁이는 이 로봇이 정상 작동하는지 구별하지 못한다. 1->6으로 가는 것과 구분이 되지 않기 때문이다. 따라서 준혁이는 오른쪽으로 움직인 뒤에는 무조건 왼쪽으로, 왼쪽으로 움직인 뒤에는 무조건 오른쪽으로 움직이도록 이동 순서를 정했다. 물론, 처음에 어느 방향으로 움직이는지는 상관없다.

준혁이는 이왕 이동하는 김에, 수직선 위에 모든 점에 정확히 한번 도착하여 정지하도록 이동 순서를 정하고 싶다. 그 말인즉 정확히 N-1번의 움직임을 통해 모든 점을 정확히 한번 방문하겠다는 뜻이다.

또한 준혁이는 처음에 로봇을 놓을 위치 S와, 로봇이 최종에 정지할 위치 E도 정했다.

S에서부터 시작에 E로 가면서, 모든 점을 정확히 한번씩 주어진 조건에 따라 방문할 수 있는 순서의 개수를 구하시오.

답이 너무 커질 수 있으므로 10^9+7로 나눈 나머지를 구하시오.

#5424 upload 23 done 8 how_to_reg 7

왔다갔다 timer 1s memory 1024MB

#5424

왔다갔다 1s 1024MB