16153번 - 비트와 가희

다음과 같은 조건이 N개 주어진다.

• i번째 bit가 1이어야 한다. 즉, 어떠한 수 X가 있다면 X & (1 << i)의 값이 0이 아니어야 한다.

1 이상 B 이하의 정수 중 이러한 조건을 만족하는 A의 배수는 몇 개인지 구하는 프로그램을 작성하시오.

첫째 줄에 N(0 ≤ N < 32), A, B(0 < A, B < 2³¹)가 공백으로 구분되어 주어진다.

둘째 줄부터 N개의 각 줄에는 켜져야 하는 bit가 N개 주어진다. 이 값들은 30이하인 음이 아닌 정수이며, 켜져야 하는 bit는 중복으로 주어지지 않는 것이 보장된다.

1이상 B이하의 정수 중 주어진 N개의 조건들을 만족하는 A의 배수의 개수를 출력하라.