아름다운 성적표
시간 제한1초메모리 제한1024 MB
네 종류 학점의 개수가 주어질 때, 정확히 K개의 대칭 쌍을 이루도록 재배열하는 서로 다른 문자열의 개수를 10^9+7로 나눈 나머지로 구한다.
문제
개발에 빠져 살던 준이는 이번 학기 성적표를 받았다. 이번 학기에는 A학점 개, B학점 개, C학점 개, D학점 개를 받았다. 성적표를 보던 준이는 학점 순서가 뒤죽박죽인 것을 보고는 성적표가 아름답지 않다고 생각했다. 그래서 학점들의 순서를 재배열하여 자신만의 아름다운 성적표를 만들기로 했다.
준이가 생각하는 아름다움의 기준은 대칭성이다. 길이가 인 성적표에서 번째 학점과 번째 학점이 동일할 때, 이를 대칭 쌍이라고 부른다. 예를 들어, 성적표의 학점 순서가 ABCA라면 첫 번째 학점 A와 네 번째 학점 A가 대칭을 이루므로 개의 대칭 쌍을 가진다.
준이는 학점들의 순서를 재배열했을 때, 정확히 개의 대칭 쌍을 갖는 성적표를 몇 가지나 만들 수 있는지 궁금해졌다. 준이를 도와 가능한 경우의 수를 구해보자. 단, 같은 학점을 받은 과목들은 서로 구별되지 않는다.
입력
첫 번째 줄에 각 학점의 개수 과 목표하는 대칭 쌍의 개수 가 공백으로 구분되어 주어진다. 은 항상 짝수이다. (; )
두 번째 줄에 , , , 가 공백으로 구분되어 주어진다. ()
출력
학점들을 순서를 재배열했을 때, 정확히 개의 대칭 쌍을 갖는 문자열을 만들 수 있는 경우의 수를 출력한다. 단, 값이 너무 커질 수 있으니 로 나눈 나머지를 출력한다.