Polynomial

Gyeonggeun likes mathematics. He likes it so much that he wrote a program to evaluate polynomials quickly. Given a polynomial f(x) in the unknown x, substituting k for x to obtain f(k) is called evaluation. However, the program Gyeonggeun wrote evaluates each term of the polynomial separately and adds them up, so each evaluation of a polynomial took time proportional to the square of its degree. To cut the computation time even a little, Gyeonggeun decides to improve his polynomial evaluation algorithm and optimize its performance.

The idea Gyeonggeun came up with is this. "How about repeating: add a value, multiply by a coefficient, add a value, multiply by a coefficient?"

For example, evaluating x4 + 2x3 + 3x2 + 4x + 5 the way Gyeonggeun's program does takes 4 additions and 9 multiplications, but with his new idea the polynomial can be rewritten as x(x(x(x + 2) + 3) + 4) + 5, which uses 4 additions and 3 multiplications, a large reduction in the number of operations.

Help Gyeonggeun submit an improved version of the polynomial computation program. Improving the performance of the polynomial computation program keeps it from exceeding the time limit.

The first line gives the degree of the polynomial N and the integer x to evaluate at. (1 ≤ N ≤ 106, 0 ≤ x ≤ 108)

From the second line to the N + 2-th line, the information Ai, i for each term of the polynomial is given. Ai is the coefficient of the term and i is the degree of the term. Each coefficient is an integer between 0 and 100 inclusive.

The degrees from the second line to the N + 2-th line are N, N − 1, ..., 0.

Evaluate the polynomial and print the result modulo 109 + 7.

If your input and output are slow, reading or writing many lines can cause a time limit exceeded verdict.

If you use C++ and want to use cin/cout, apply both cin.tie(NULL) and sync_with_stdio(false), and use the newline character (\n) instead of endl. Note that once you do this, you must no longer use C input and output such as scanf/printf/puts/getchar/putchar.

If you use Java, you can use BufferedReader and BufferedWriter instead of Scanner and System.out.println. Call BufferedWriter.flush only once at the very end.

If you use Python, you can use sys.stdin.readline instead of input.

Finally, Pypy3 has the same syntax as Python 3 and generally runs faster. If you want to use Python on a problem with many operations, submitting with Pypy is recommended.