Counting - Coin Combination Problem II

Time Limit : 3 sec, Memory Limit : 262144 KB

コインの組み合わせ II

N 枚のコインがあります。それぞれのコインの値段はai 円です。E 君は, ちょうどK 個のコインを得たいと思っていて, 値段の合計はL 円以上 R 円以下にしたいと思っています。このようなコインの選び方は何通りあるでしょうか? ただし, それぞれのコインは区別するものとします。

Constraints

  • 1 ≤ KN ≤ 40
  • 1 ≤ ai ≤ 1016
  • 1 ≤ LR ≤ 1016

Input

入力は, 以下の形式で与えられる。

N K L R
a1 a2 ... aN

Output

選び方の総数を 1 行に出力しなさい。

Sample Input 1

2 2 1 9
5 1

Sample Output 1

1

Sample Input 2

5 2 7 19
3 5 4 2 2

Sample Output 2

5