시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

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

  1. 먼저 로봇은 L/(L+M+R)의 확률로 자신이 바라보는 방향의 왼쪽으로 90도 돌고, M/(L+M+R)의 확률로 방향을 바꾸지 않으며, R/(L+M+R)의 확률로 자신이 바라보는 방향의 오른쪽으로 90도 돈다.
    • 예를 들어, 처음 상태에서는 로봇이 왼쪽으로 90도 돌면 y축 양의 방향을 바라보게 되고, 오른쪽으로 90도 돌면 y축 음의 방향을 바라보게 된다.
  2. 1번 과정이 끝나고 나서, 로봇은 자신이 바라보고 있는 방향으로 1의 거리를 움직인다.

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

입력

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

출력

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

예제 입력

5 1 0 1

예제 출력

5

예제 입력 2

10 5 0 7

예제 출력 2

308301433

예제 입력 3

15 249 123 953

예제 출력 3

644460144

예제 입력 4

100 4 5 6

예제 출력 4

648224530

힌트

출처

Contest > kriiicon > 제 4회 kriiicon 4번