정올이는 롤플레잉 게임을 하고 있다.

이 게임에서 캐릭터는 N개의 장비 슬롯을 가지는데, 각 슬롯에는 하나의 장비만 장착이 가능하다.

또한 장비는 아무 슬롯에나 장착 할 수 없으며 장비마다 정해진 하나의 슬롯에만 장착이 가능하다.

어떤 슬롯은 필수 장착 슬롯으로, q_i 가 1인 경우 i번째 슬롯에는 항상 장비가 장착되어 있어야 한다.

모든 장비는 1 이상의 정수로 이루어진 [강화레벨] 이라는 값을 가지고 있는데,

캐릭터의 장비 슬롯은 무기 슬롯과 같이 중요한 슬롯이 있고, 장갑 슬롯처럼 덜 중요한 슬롯이 있기 때문에

캐릭터의 전투력은 각 슬롯의 중요도 w_i와 그 슬롯에 장착된 장비 강화레벨의 곱들의 합으로 계산된다.

예를 들어 1번 슬롯의 중요도가 3, 2번 슬롯의 중요도가 1인 경우,

1번 슬롯에 강화레벨 3의 장비를 장착하면 전투력 3*3=9를 얻고,

2번 슬롯에 강화레벨 2의 장비를 장착하면 전투력 1*2=2를 얻게되어

캐릭터의 전투력은 9+2 = 11이 된다.

겁이 많은 정올이는 자신보다 전투력이 낮거나 같은 캐릭터와 전투를 하고 싶다.

정올이의 전투력이 S라고 할 때, 상대방의 전투력이 S이하가 되는 장비 강화레벨 조합이 얼마나 많은지 계산해보자.

[제약 조건]

1 ≤ N ≤ 20

0 ≤ S ≤ 1,000,000

1 ≤ w_i ≤ 20

0 ≤ q_i ≤ 1

장비 조합 timer 1s memory 128MB

장비 조합 1s 128MB