問題一覧 > 通常問題

No.1662 (ox) Alternative

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : 👑 箱箱 / テスター : LayCurseLayCurse 👑 ygussanyygussany
3 ProblemId : 6750 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 00:13:12

問題文

$A$ 個の ( 、$B$ 個の ) 、$C$ 個の o 、$D$ 個の x からなる長さ $A+B+C+D$ の文字列のうち、次の条件を満たすものの個数を $10^9+7$ で割った余りを求めてください。

  • 登場するすべての o を () に、x を )( に置き換えて得られる文字列は括弧の対応が取れている文字列である。

$T$ 個のテストケースについて答えてください。

▼ (括弧の対応が取れている文字列の定義)

括弧の対応が取れている文字列とは、次のうちいずれかの条件を満たす文字列です。

  • 空文字列
  • ある括弧の対応が取れている空でない文字列 $s,t$ が存在し、$s,t$ をこの順に連結した文字列
  • ある括弧の対応が取れている文字列 $s$ が存在し、(, $s$, ) をこの順に連結した文字列

制約

  • $1\le T\le 10^5$
  • $0\le A,B,C,D\le 10^5$
  • $A+B+C+D\ge 1$
  • 入力はすべて整数

入力

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

各テストケースは以下の形式で与えられます。 

$A$ $B$ $C$ $D$

出力

$T$ 行出力してください。$i$ 行目には、$i$ 番目のテストケースに対する答えを出力してください。

サンプル

サンプル1
入力
3
1 1 1 1
31 41 59 26
999 999 0 1234
出力
4
0
479533106

($1$ つ目のテストケース) (ox), (xo), o(x), (x)o の $4$ 通りがあります。

($2$ つ目のテストケース) $1$ つも存在しません。

($3$ つ目のテストケース) $10^9+7$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。