문제

영화 오펜하이머를 아는가. 그렇다. 오펜하이머가 핵폭탄을 만드는 러닝타임이 3시간이 되는 영화다. 김민아는 수강신청을 실패했다. 3시간짜리 영화를 보기 위해서는 수업을 째야하는 지경에 이르렀다. 이에 화가 난 김민아는 자신이 오펜하이머가 되어 학교를 날려버리기로 했다. 기술의 한계로 핵폭탄은 아니지만, 여러 혹은 하나의 화약을 조합하여 폭탄을 만들 수 있다.

화약들은 처음부터 화약, 화약 순으로 이름이 붙는다. 또한 각 화약의 세기가 양의 정수로 주어진다. 화약 옆에 붙는 숫자가 작은 화약일수록 주요한 성분이 되기에, 다른 화약에 의해 성질이 바뀌면 안된다. 그러기 위해서는 화약의 세기는 적어도 화약의 배 이상은 강력해야한다. 예를 들어, 이 인 경우, 의 세기를 가진 화약을 조합하는 것은 가능하지만, 의 세기를 보이는 화약의 조합으로는 폭탄을 만들지 못한다.

또한 국제법에 의거하여 개인이 세기 을 넘는 강한 화약을 가지거나 가공하는 것은 불법이다. 법의 테두리 안에서 민아가 폭탄을 만들 수 있는 경우의 수를 알려주자.

입력

첫째 줄에 과 이 공백에 걸쳐 주어진다.

출력

폭탄을 만들 수 있는 경우의 수를 로 나눈 값을 출력한다.