로봇 Batch Compilation commands

$xy$평면의 원점에 로봇이 서 있다. 로봇은 $x$축 양의 방향을 바라보고 있으며, 지금부터 $N $번 움직이려고 한다. 로봇이 한 번 움직이는 과정은 다음과 같다.

1. 먼저 로봇은 의 확률로 자신이 바라보는 방향의 왼쪽으로 90도 돌고, 의 확률로 방향을 바꾸지 않으며, 의 확률로 자신이 바라보는 방향의 오른쪽으로 90도 돈다.

• 예를 들어, 처음 상태에서는 로봇이 왼쪽으로 90도 돌면 $y$축 양의 방향을 바라보게 되고, 오른쪽으로 90도 돌면 $y$축 음의 방향을 바라보게 된다.

2. 1번 과정이 끝나고 나서, 로봇은 자신이 바라보고 있는 방향으로 $1$의 거리를 움직인다.

로봇이 $N$번 움직인 결과 좌표 $(x, y)$에 위치해 있다면, 로봇이 원점으로부터 떨어져 있는 정도는 $x^{2} + y^{2}$로 나타난다. 로봇이 $N $번 움직인 다음 원점으로부터 떨어져 있는 정도의 기댓값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에는 로봇이 움직일 횟수, 왼쪽으로 방향을 바꿀 확률, 가만히 있을 확률, 오른쪽으로 방향을 바꿀 확률을 결정하는 네 정수 $N, L, M, R$이 공백으로 구분되어 주어진다. $L, M, R$ 중 적어도 하나는 양의 정수이다.

부분문제

부분문제	점수	N	L, M, R
1	4	1 ≤ N ≤ 15	0 ≤ L, M, R ≤ 106
2	96	1 ≤ N ≤ 109	0 ≤ L, M, R ≤ 106

출력

로봇이 $N $번 이동한 다음 원점으로부터 떨어져 있는 정도의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 가 된다면, 을 대신 출력하도록 한다. $b^{-1}$은 $b$의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

입출력 예제

예제 1

입력

5 1 0 1

출력

5

예제 2

입력

10 5 0 7

출력

308301433

예제 3

입력

15 249 123 953

출력

644460144

예제 4

입력

100 4 5 6

출력

648224530