Protocol

Time limit2sMemory limit256 MB

Summary

Starting from one wire of capacity N, each year every wire splits into two wires transformed by two quadratic polynomials, and after M years we need the sum of 112345 raised to each wire's capacity, mod 1e9+9.

Level: Hard8 of 10
Topics: Math, Divide and conquer, Combinatorics, Recursion
Solved: No attempts yet

Problem

Risha lives in the country of Meiji and built a communication system that runs over wires. In the protocol Risha wrote, every wire has a fixed capacity, and a wire of capacity $i$ carries $i$ characters.

Meiji uses 112345 different characters. A wire of capacity $i$ therefore sends one of $112345^i$ messages, and the value of that wire is $112345^i$ .

Meiji has many engineers besides Risha. Every year they take every wire in the country and cut it into two wires with the Banach-Tarski paradox. One wire of capacity $X$ becomes a wire of capacity $f(X) = aX^2 + bX + c$ and a wire of capacity $g(X) = dX^2 + eX + f$ . Start with a single wire of capacity $N$ . After one year there are two wires, with capacities $f(N)$ and $g(N)$ . After two years there are four wires, with capacities $f(f(N))$ , $f(g(N))$ , $g(f(N))$ and $g(g(N))$ . After $M$ years there are $2^M$ wires built the same way. Find the sum of the values of all wires after $M$ years.

Input

The first line contains $N$ and $M$ , separated by a space.

The second line contains $a$ , $b$ , $c$ , $d$ , $e$ , $f$ , separated by spaces.

All values satisfy $0 \le N, M, a, b, c, d, e, f \le 1000000000 = 10^9$ .

Output

Print the sum of the values of all wires after $M$ years, modulo $1000000009 (= 10^9 + 9)$ .

Hint

In the first example the total value of the wires is $112345^3 + 112345^6$ .

Examples2

Example 1
Input
```
0 1
1 2 3 4 5 6
```
Expected output
```
844207762
```
Example 2
Input
```
0 2
1 0 0 0 0 1
```
Expected output
```
337036
```