33838번 - 사라져버릴 것 같아요

문제

오늘은 전국의 실력자들이 모여 벌이는 전설의 알고리즘 대회, 월간 향유회가 열리는 날이다. 참가자들은 아래의 조건에 따라 $N$개의 자리가 일렬로 있는 긴 책상에 앉아야 한다.

각 참가자는 세 성격 유형 중 하나를 가진다.

• 내향형: 양옆 자리에 모두 사람이 없어야 한다.
• 균형형: 양옆 자리 중 정확히 한 자리에만 사람이 있어야 한다.
• 외향형: 양옆 자리에 모두 사람이 있어야 한다.

이번 대회에는 내향형 $A$명, 균형형 $B$명, 외향형 $C$명의 사람들이 참가한다. 이들을 $N$개의 자리에 모두 배치하는 경우의 수를 구해보자.

모든 참가자는 정확히 한 자리에 앉으며, 한 자리에는 한 명만 앉을 수 있다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 100,000円)$

두 번째 줄부터 $T$개의 줄에 걸쳐 자리의 수 $N$과 내향형, 균형형, 외향형 참가자의 수 $A,ドル $B,ドル $C$가 공백으로 구분되어 주어진다. $(1 \le N, A, B, C \le 100,000円)$

출력

각 테스트 케이스마다 조건을 만족하도록 참가자들을 배치하는 경우의 수를 10ドル^9 + 7$로 나눈 나머지를 한 줄에 하나씩 출력한다.

제한

힌트