SBC 격납고

Sistema Binário de Cargas(SBC)의 소형 화물기가 특별하고 비밀스러운 물품을 운송하도록 설계되었다. 이 물품들은 다양한 무게의 상자에 담겨 있다.

비행기에는 안전 무게 범위가 있어 그 범위 안에서는 항공기가 안정적으로 비행한다. 즉, 운송하는 상자의 총 무게가 어떤 구간을 벗어나면 비행의 안정성을 보장할 수 없다.

모든 상자의 무게는 서로 다르다. 또한 두 상자에 대해 무거운 상자는 가벼운 상자보다 적어도 두 배 무겁다.

비행기를 불안정하게 만들지 않으면서 지정된 개수의 상자를 골라 운송하는 방법의 수를 구하시오.

입력의 첫째 줄에는 두 정수 N과 K가 주어진다. 각각 사용할 수 있는 상자의 개수와 비행기에 실어야 하는 상자의 개수이다.

둘째 줄에는 N개의 정수가 공백으로 구분되어 주어지며, 상자의 무게를 나타낸다.

셋째 줄에는 두 정수 A와 B가 주어지며, 이는 안전 무게 범위인 폐구간 [A, B]를 나타낸다.

주어지는 모든 무게는 같은 단위이다.

출력은 한 줄로, 비행을 위험에 빠뜨리지 않으면서 지정된 개수의 상자를 고르는 서로 다른 방법의 수를 출력한다.

• 1 ≤ N ≤ 50.
• 1 ≤ K ≤ 50.
• 각 상자의 무게 P는 1 ≤ P ≤ 10^18.
• 1 ≤ A ≤ B ≤ 2 × 10^18.