시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 28 17 16 69.565%

문제

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

예제 입력

0 1
1 2 3 4 5 6

예제 출력

844207762

예제 입력 2

0 2
1 0 0 0 0 1

예제 출력 2

337036

힌트

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