아름다운 성적표

시간 제한1초메모리 제한1024 MB

요약
네 종류 학점의 개수가 주어질 때, 정확히 K개의 대칭 쌍을 이루도록 재배열하는 서로 다른 문자열의 개수를 10^9+7로 나눈 나머지로 구한다.
난이도

어려움10점 중 8점

유형
조합론, 수학, 동적 계획법
정답자
아직 제출이 없습니다

문제

개발에 빠져 살던 준이는 이번 학기 성적표를 받았다. 이번 학기에는 A학점 aa개, B학점 bb개, C학점 cc개, D학점 dd개를 받았다. 성적표를 보던 준이는 학점 순서가 뒤죽박죽인 것을 보고는 성적표가 아름답지 않다고 생각했다. 그래서 학점들의 순서를 재배열하여 자신만의 아름다운 성적표를 만들기로 했다.

준이가 생각하는 아름다움의 기준은 대칭성이다. 길이가 NN인 성적표에서 ii번째 학점과 N−i+1N-i+1번째 학점이 동일할 때, 이를 대칭 쌍이라고 부른다. 예를 들어, 성적표의 학점 순서가 ABCA라면 첫 번째 학점 A와 네 번째 학점 A가 대칭을 이루므로 11개의 대칭 쌍을 가진다.

준이는 학점들의 순서를 재배열했을 때, 정확히 KK개의 대칭 쌍을 갖는 성적표를 몇 가지나 만들 수 있는지 궁금해졌다. 준이를 도와 가능한 경우의 수를 구해보자. 단, 같은 학점을 받은 과목들은 서로 구별되지 않는다.

입력

첫 번째 줄에 각 학점의 개수 NN과 목표하는 대칭 쌍의 개수 KK가 공백으로 구분되어 주어진다. NN은 항상 짝수이다. (2≤N≤200,0002 \leq N \leq 200\\,000; 0≤K≤N20 \leq K \leq \frac{N}{2})

두 번째 줄에 aa, bb, cc, dd가 공백으로 구분되어 주어진다. (0≤a,b,c,d≤N;a+b+c+d=N0 \leq a, b, c, d \leq N; a+b+c+d=N)

출력

학점들을 순서를 재배열했을 때, 정확히 kk개의 대칭 쌍을 갖는 문자열을 만들 수 있는 경우의 수를 출력한다. 단, 값이 너무 커질 수 있으니 109+710^9 + 7로 나눈 나머지를 출력한다.

예제4

  1. 예제 1

    입력
    4 1
    2 1 1 0
    
    예상 출력
    4
    
  2. 예제 2

    입력
    10 3
    3 2 3 2
    
    예상 출력
    960
    
  3. 예제 3

    입력
    12 0
    2 4 3 3
    
    예상 출력
    76800
    
  4. 예제 4

    입력
    10 5
    3 2 3 2
    
    예상 출력
    0