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

문제

TingTing is a girl that loves matrices. One day, she wants to use a computer to generate a giant n row by m column matrix (you don't have to worry about how she'll store it). Her generated matrix will satisfy a mystical property: if we use F[i][j] to represent the cell in the i-th row and j-th column, then F[i][j] will satisfy the following system of equations:

where abc, and d are given constants.

TingTing would like to know the value of F[n][m] and she would like you to help her. Since the final value may be very large, you are only required to output it modulo 1,000,000,007.

입력

The input will contain the six integers nmabc, and d.

출력

Output a single integer, the value of F[i][j] modulo 1,000,000,007.

제한

  • 1 ≤ nm ≤ 101,000,000
  • 1 ≤ abcd ≤ 109

예제 입력 1

3 4 1 3 2 6

예제 출력 1

85