Protocol

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.

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$.

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

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