Một dãy Fibonacci tổng quát được xác định bởi công thức:

\[ a_n = p \times a_{n-1} + q \times a_{n-2} \]

Cho trước:

• Hệ số \(p\), \(q\)
• Hai phần tử đầu tiên \(a_1\), \(a_2\)
• Hai số nguyên \(n\) và \(m\)

Yêu cầu: Tính \(a_n \bmod m\)

Định dạng vào

• Một dòng gồm 6 số nguyên cách nhau bởi dấu cách:
• \(p\) \(q\) \(a_1\) \(a_2\) \(n\) \(m\)

Định dạng ra

• Một số nguyên: \(a_n \bmod m\)

Input

1 1 1 1 10 7

Output

6

Giải thích

Dãy Fibonacci truyền thống bắt đầu từ 1,1:

• \(a_3 = 1+1 = 2\)
• \(a_4 = 1+2 = 3\)
• \(a_5 = 2+3 = 5\)
• \(a_6 = 3+5 = 8\)
• ...
• \(a_{10} = 55\)

\[ 55 \bmod 7 = 6 \]

Ràng buộc

• \(p, q, a_1, a_2 \in [0, 2^{31} - 1]\)
• \(1 \le n, m \le 2^{31} - 1\)