問題一覧 > 通常問題

No.122 傾向と対策:門松列(その3)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : LayCurseLayCurse
2 ProblemId : 298 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:36:17

問題文

ここ数日で門松列に関する問題が頻出しております.
ここでは演習を通じて,門松列に対する理解を深め,門松列の問題が出題された時に解けるようになっておきましょう.
門松列対策講座を受講される皆様は既にご存知かと思いますが,門松列とは 3 個の要素からなる数列 a,b,c で以下の 2 つの条件を満たすものです.
a,b,c は全て異なる
3 つの要素の中で b が最も大きい,または,b が最も小さい

この問題では通常の門松列ではなく,最近ブームになりつつあるスーパーリッチ門松列を考えましょう.
スーパーリッチ門松列とは 7 個の要素からなる数列 a,b,c,d,e,f,g で以下の 2 つの条件を満たすものです.
a,b,c,d,e,f,g は全て異なる
min(b,d,f)>max(a,c,e,g) または max(b,d,f)<min(a,c,e,g)
(直感的には,全要素異なり,偶数番目の要素が小さい方から3つ,または,大きい方から3つになっているということです.ジグジグザグザグ)

由岐さんは得体の知らないものをよく知るための第一歩は数えることだと思っています.
そこで,各要素 x=a,b,c,d,e,f,g の下限 xmin と上限 xmax が与えられるので,xminxxmax を満たし,更に全ての要素が整数からなるスーパーリッチ門松列の数を数えるプログラムを書いてください.
ただし,答えは大きくなるかもしれないので答えを 109+7 で割った余りを出力してください.

入力

amin amax
bmin bmax
cmin cmax
dmin dmax
emin emax
fmin fmax
gmin gmax

1xminxmax20000=2×104x=a,b,c,d,e,f,g

出力

条件を満たすスーパーリッチ門松列の数 modulo 109+7 の値を出力してください.

サンプル

サンプル1
入力
6 8
3 10
7 10
8 12
4 10
1 9
7 16
出力
8

条件を満たすスーパーリッチ門松列は以下の 8 個です:
6,10,7,11,4,9,8
6,10,7,11,5,9,8
6,10,7,12,4,9,8
6,10,7,12,5,9,8
6,10,8,11,4,9,7
6,10,8,11,5,9,7
6,10,8,12,4,9,7
6,10,8,12,5,9,7

サンプル2
入力
1 7
1 7
1 7
1 7
1 7
1 7
1 7
出力
288

3!×4!×2 になるらしい.
あ,そうか,この場合,置換で,b,d,f が大きいか小さいかの 2 通りで,b,d,f の並び替え方 3! で,a,c,e,g の並び替え方 4! 通りだもんね.

サンプル3
入力
1 20000
1 20000
1 20000
1 20000
1 20000
1 20000
1 20000
出力
96826092

最大ケースです.
109+7 で割った余りを出力することを忘れないで下さい.

サンプル4
入力
2012 2019
2011 2017
2011 2018
2012 2019
2015 2015
2008 2018
2006 2019
出力
2015

新年あけましておめでとうございます.

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