No.1043 直列大学

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 172
作問者 : SuunnSuunn / テスター : ricky_quikemricky_quikem
9 ProblemId : 3620 / 出題時の順位表
問題文最終更新日: 2020-01-05 19:00:42

問題文

 高橋くんは直列大学(略称:直大)の学生です。

 直列大学の今日の実験は、乾電池と豆電球を使った実験です。この実験では、$N$個の乾電池と$M$個の豆電球が用意されており、$i$番目の乾電池の電圧は$V_i$、$j$番目の豆電球の抵抗値は$R_j$です。今日高橋くんがすべきことは、用意された乾電池と豆電球からそれぞれ自由な数を選んで直列につなぎ、豆電球を光らせることです。

 豆電球は、$A$以上の電流を流さないと光りません。一方で、$B$より大きい電流を流すと危険なので、流す電流は$B$以下にする必要があります。ただし、豆電球に流れる電流の値は、(つないだ乾電池の電圧の総和)$/$(つないだ豆電球の抵抗値の総和)で表されます。

 高橋くんはどのように乾電池と豆電球を選んだらよいかわからなくなったので、高橋くんが選ぶべき乾電池と豆電球の組み合わせの個数を$1000000007$で割ったあまりを求めてください。ただし、$2$つの組み合わせが異なるとは、片方だけに使われている乾電池または豆電球があることを意味しており、乾電池や豆電球をつなぐ順番は関係ないことに注意してください。

(注意)Pythonでは実行時間が厳しく、writer/testerはACを取れていません。PyPyでAC可能なことは確認済みなので、Pythonで提出する際はPyPyを選択することをお勧めします。

入力

$N\ M$
$V_1\ V_2\ \dots\ V_N$
$R_1\ R_2\ \dots\ R_M$
$A\ B$

$1 \le N,M \le 100$
$1 \le V_i,R_j \le 1000$
$1 \le A\le B \le 10^5$
入力は全て整数である

出力

高橋くんが安全に豆電球を光らせることができるような乾電池と豆電球の組み合わせの個数を、$1000000007$で割ったあまりを出力してください。

サンプル

サンプル1
入力
2 2
5 10
1 1
3 100
出力
8

乾電池と豆電球をそれぞれ1つ以上選ぶような方法の中で、$(V_1,R_1,R_2)$を選んだときだけ条件を満たしません。

サンプル2
入力
1 1
100
1
1 1
出力
0

条件を満たす組み合わせがないこともあります。

サンプル3
入力
5 5
1 2 3 4 5
1 2 3 4 5
1 5
出力
489

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