하노이 탑

하노이 탑에서는 세 막대 중 한 막대에 쌓인 n개의 원판을 다른 막대로 옮긴다. 원판은 한 번에 하나만 움직일 수 있고, 작은 원판 위에 큰 원판을 올릴 수 없다. 모든 원판을 한 막대에서 다른 막대로 옮기는 데 필요한 최소 이동 횟수는 2^n - 1이다.

동혁이는 원판을 옮기다가 실수해서 세 막대에 원판이 나뉘어 놓이게 되었다. 그래도 하노이 탑의 규칙은 어기지 않았으므로, 각 막대에서는 아래에서 위로 갈수록 원판 번호가 작아진다.

현재 상태에서 모든 원판을 하나의 막대에 모으려고 한다. 어떤 막대에 모아야 최소가 되는지와 그때의 최소 이동 횟수를 구하라. 이동 횟수가 매우 클 수 있으므로 1,000,000으로 나눈 나머지를 출력한다.

첫째 줄에 원판의 개수 n(1 <= n <= 100,000)이 주어진다.

둘째 줄에 세 정수 a, b, c가 주어진다. 각각 1번, 2번, 3번 막대에 꽂혀 있는 원판의 개수이다. 각 값은 0 이상 n 이하이고, a + b + c = n이다.

다음 세 줄에는 1번, 2번, 3번 막대에 있는 원판 번호가 차례대로 주어진다. 각 줄의 번호는 해당 막대의 아래쪽 원판부터 위쪽 원판 순서이다. 원판 번호는 1부터 n까지이며, 입력은 항상 올바른 상태만 주어진다.

첫째 줄에 모든 원판을 모아야 하는 막대 번호를 출력한다.

둘째 줄에 최소 이동 횟수를 1,000,000으로 나눈 나머지를 출력한다.