문제
옛날 유럽에 코이(Koi)라는 나라가 있었다. 왕은 평소에 주변의 소국을 정복하는 삶을 살아왔다. 왕에겐 네 명의 왕자들이 있었는데, 왕은 그들이 서로 사이좋게 지내길 바랬다. 그래서 어느 날, 왕과 왕자 넷이 힘을 합쳐서 다른 소국을 정복하기로 했다. 왕의 계획은 K개의 주변 소국을 왕자들과 함께 정복하는 것이다.
왕에겐 N개의 전투부대가 있고, 각 전투부대마다 편성된 병사 수가 다르다. 한 전투부대로 두 개의 소국을 담당하기엔 그 부대의 피로가 너무 커지고, 사기가 꺾여서 전쟁을 질 수도 있기 때문에, 왕은 전투마다 각각 다른 부대를 데리고 나간다. 왕은 부대를 2개 분대(부대보다 작은 단위의 병사 집합)로 나눠서 한 분대는 자기가 통솔하고, 나머지 한 분대의 통솔권을 아들들에게 주려고 한다. 그러나, 왕자들의 분대는 구성원의 인원수 4로 나누어 떨어져야 한다. 그래야 4명이 동등하게 나누어서 통솔할 수 있다. 그렇게 하지 않으면, 왕자들끼리 자기들이 잘났다고 싸우다가 전쟁을 패배하게 된다.
왕이 K개의 전투부대를 뽑아 각 부대들을 왕과 왕자들의 분대인 두 분대로 나누는 모든 경우의 수를 구하여라. 답이 클 수 있기 때문에, 10억 7로 나눈 나머지를 구한다.
각 전투부대마다의 병사들은 모두 다르게 구분한다. 따라서, 예를 들어서 5명으로 구성된 부대라면, {1(번 병사}, 2, 3, 4, 5}의 병사들이 있다고 할 수 있다. 왕자들의 분대가 {1, 2, 3, 4}가 되는 것과 {1, 2, 3, 5}가 되는 것은 각각 다른 경우로 친다. 또한, 왕자들에게 아무 병력도 주지 않고, 왕 혼자서 통솔하거나, 왕은 지켜보고 왕자들만 병력을 통솔하는 것도 가능한 경우로 친다.
입력
첫 줄에 N과 K가 주어진다. N은 1이상 10,000 이하의 정수이며, K는 1 이상 min(100, N) 이하이다.
다음 줄에 N개의 전투부대 병사 수가 주어진다. 병사 수는 1이상 109 이하이다.
[제한사항]
30%의 입력 데이터에 있어서 병사 수는 1이상 105 이하이다.
출력
N개 부대에서 K개를 뽑아, 각 부대들을 왕과 왕자들의 분대인 두 분대로 나누는 모든 경우의 수를 109+7로 나눈 나머지를 출력한다.
예제
3 2
3 4 5
20
로그인해야 코드를 작성할 수 있어요.