개미

개미 한 마리가 정육면체 $ABCDEFGH$의 모서리를 따라 걷습니다.

개미는 주어진 한 꼭짓점에서 다른 한 꼭짓점까지 정확히 $k$개의 모서리를 지나 가는 방법이 몇 가지인지 알고 싶어 합니다. (개미는 한 모서리에 들어서면 도중에 되돌아가지 않고 반드시 그 모서리의 반대쪽 끝까지 갑니다.) 어떤 모서리를 $x$번 지나면 그 모서리는 $x$번으로 셉니다.

개미는 흥미로운 경로만 세고 싶어 합니다. 즉, 어떤 꼭짓점에 도착하면 그 꼭짓점으로 들어올 때 방금 사용한 모서리와는 다른 모서리로 나가려 합니다 (같은 모서리를 연속해서 두 번 사용하지 않습니다).

개미는 어떤 $p$에 대해 $0$부터 $p - 1$까지의 정수만 셀 수 있으므로, 답을 $p$로 나눈 나머지를 구하세요.

정육면체의 구조는 다음과 같습니다: 아랫면은 정사각형 $ABCD$(모서리 $AB$, $BC$, $CD$, $DA$), 윗면은 정사각형 $EFGH$(모서리 $EF$, $FG$, $GH$, $HE$)이며, 두 면을 잇는 수직 모서리는 $AE$, $BF$, $CG$, $DH$입니다 (모서리는 모두 12개).

다음을 수행하는 프로그램을 작성하세요:

• 시작 꼭짓점, 끝 꼭짓점, 경로의 모서리 개수, 정수 $p$를 입력받는다,
• 위 조건을 만족하는 흥미로운 경로의 수를 $p$로 나눈 나머지를 계산한다,
• 그 답을 표준 출력에 쓴다.

첫째 줄에 대문자 알파벳 두 개 $v_1$과 $v_2$가 공백 하나로 구분되어 주어집니다 ($A \le v_1, v_2 \le H$, $v_1 \ne v_2$). 각각 개미가 출발하는 꼭짓점과 도착하는 꼭짓점을 나타냅니다. 둘째 줄에 두 정수 $k$와 $p$가 공백 하나로 구분되어 주어집니다 ($1 \le k \le 2\,000\,000\,000$, $2 \le p \le 1\,000\,000\,000$).

꼭짓점 $v_1$에서 꼭짓점 $v_2$까지 정확히 $k$개의 모서리로 이루어진 흥미로운 경로의 수를 $p$로 나눈 나머지를 정수 하나로 표준 출력에 출력하세요.