14559번 - Protocol

문제

메이지 나라에 사는 리샤는 전선을 이용한 통신 시스템을 만들었다. 리샤가 만든 통신 규약에 따르면 모든 전선에는 각자 정해진 용량이 있고, 전선의 용량이 $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$이다.