통신 규약

메이지 나라에 사는 리샤는 전선으로 통신하는 시스템을 만들었다. 리샤가 정한 통신 규약에서 모든 전선은 정해진 용량이 있고, 용량이 $i$인 전선은 문자 $i$개를 보낸다.

메이지 나라에서 쓰는 문자는 112345종류다. 그래서 용량이 $i$인 전선은 $112345^i$가지의 정보를 보내고, 이 전선의 가치는 $112345^i$다.

메이지 나라에는 리샤 말고도 공학자가 많다. 공학자들은 해마다 나라 안의 모든 전선을 바나흐-타르스키 역설로 두 개씩 쪼갠다. 용량이 $X$인 전선 하나는 용량이 $f(X) = aX^2 + bX + c$인 전선과 용량이 $g(X) = dX^2 + eX + f$인 전선이 된다. 용량이 $N$인 전선 하나로 시작하면 1년 뒤에는 용량이 $f(N)$, $g(N)$인 전선 두 개가 있고, 2년 뒤에는 용량이 $f(f(N))$, $f(g(N))$, $g(f(N))$, $g(g(N))$인 전선 네 개가 있다. 이렇게 $M$년이 지나면 전선 $2^M$개가 있다. $M$년 뒤 전선의 가치를 모두 더한 값을 구하라.

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

둘째 줄에 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 주어진다.

모든 값은 $0 \le N, M, a, b, c, d, e, f \le 1000000000 = 10^9$을 만족한다.

$M$년 뒤 전선의 가치를 모두 더한 값을 $1000000009 (= 10^9 + 9)$로 나눈 나머지를 출력한다.

첫 번째 예제에서 전선 가치의 총합은 $112345^3 + 112345^6$이다.