Hàm G(x) được định nghĩa như sau:

~G(x) = x^2 + 2x + 3~

Tất nhiên biết giá trị x ta sẽ dễ dàng tính được G(x), và việc tính hàm G lồng nhau như dưới đây cũng không quá khó:

~F(n, x) = \underbrace{G(G(G(...G(G(x))...)))}_{\text{Lồng nhau n lần}} \% 10^9~

Input:

• Hai số nguyên dương ~N~ và ~X~, giá trị không quá 1 tỉ.

Output:

• Giá trị của ~F(n, x)~

Sample Input 1

2 1

Sample Output 1

51

Sample Input 2

3 3

Sample Output 2

132498

Sample Input 3

10 123

Sample Output 3

550273643