33688번 - 불의 군주 라그나로스 2

문제

불의 세례를 받아라!

하스스톤에 등장하는 불의 군주 라그나로스는 직접 공격은 할 수 없지만 내 턴이 끝날 때 무작위 적에게 피해를 8ドル$ 주는 전설 카드다.

평소 하스스톤을 즐겨하는 '아시나요'와 '누구냐요'는 오랜만에 만나서 친선전으로 한 판 붙기로 했다. 유틸은 두 사람의 친선전이 재밌어 보여 관전하기 시작했다. 두 사람은 공방전을 치열하게 벌였고 어느덧 게임은 후반부에 접어들게 되었다. 현재 아시나요의 필드에는 불의 군주 라그나로스가 2마리 있고, 누구냐요의 필드에는 하수인이 5마리 있는 상황이다. 이번 턴이 끝날 때 불의 군주 라그나로스 중 1ドル$마리가 누구냐요의 영웅에게 피해를 입히면 승리할 수 있지만, 2마리 모두 누구냐요의 영웅에게 피해를 입히지 못하면 다음 턴에 아시나요가 무조건 패배하는 상황이다. '턴 종료'를 누르며 "경우의 수는 이기는 경우 1가지 지는 경우 1가지야!"라고 기도하는 아시나요를 보며 한심하게 느낀 유틸은 승리하는 경우의 수를 정확하게 계산하는 프로그램을 만들어 주기로 했다. 다만 하스스톤에 한정하지 않고 좀 더 일반화해서 만들기로 했다.

이해를 돕기 위해 몇 가지 용어를 간단히 정의한다.

• 영웅이란 게임 내에서 전투를 벌이는 주체를 의미한다.
• 하수인이란 전투를 벌이는 영웅의 대행자를 부르는 카드를 의미한다.
• 필드란 하수인들이 소환되어 전투를 벌일 수 있는 장소를 의미한다.
• 직접 공격이란 하수인이나 영웅이 전투를 통해 별도의 특수 효과 없이 상대 하수인이나 영웅에게 바로 피해를 주는 기본 공격 행위를 의미한다.

이제 다음과 같은 상황을 가정하자.

• 현재 자신의 필드에는 불의 군주 라그나로스가 $N$마리 있으며, 상대방의 필드에는 하수인이 $M$마리 있다.
• 상대방의 필드에 있는 하수인의 각 체력은 $H_1, H_2, \cdots, H_M$이며, 상대방 영웅의 체력은 $Y$이다.
• 불의 군주 라그나로스는 이번 턴이 끝날 때 무작위 적에게 피해를 $X$ 주는 효과를 가지고 있다. 이 효과는 다음과 같은 방법으로 처리한다.
  • 불의 군주 라그나로스 $N$마리의 효과를 한 마리씩 차례차례로 처리한다.
  • 불의 군주 라그나로스는 상대방의 하수인들과 영웅 중 하나를 선택해서 해당 하수인 혹은 영웅의 체력을 $X$ 줄인다.
  • 이 과정에서 체력이 0ドル$ 이하가 되는 하수인 혹은 영웅은 파괴되어, 더 이상 불의 군주 라그나로스의 선택 대상이 되지 않는다.
  • 상대방 영웅의 체력이 0ドル$ 이하가 되어 파괴된 경우 그 즉시 게임에서 승리한다.
• 이번 턴에 불의 군주 라그나로스의 효과 이외에 상대방의 하수인 혹은 영웅에게 피해를 주는 방법은 없다.
• 이번 턴에 상대방 영웅을 파괴하지 못한 경우 게임에서 패배한다.

이번 턴이 끝날 때 상대방 영웅의 체력이 0ドル$ 이하가 되어 게임에서 승리하는 경우의 수는 몇 가지일까?

입력

첫째 줄에 자신의 필드에 있는 불의 군주 라그나로스의 마릿수 $N,ドル 상대방의 필드에 있는 하수인의 마릿수 $M,ドル 내 턴이 끝날 때 불의 군주 라그나로스가 무작위 적에게 주는 피해 $X$와 상대방 영웅의 체력 $Y$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 50,000円; 1 \leq M \leq 50,000円; 1 \leq X \leq 50; 1 \leq Y \leq 100)$

둘째 줄에 상대방의 필드에 있는 각 하수인의 체력 $H_1, H_2, \cdots, H_M$이 공백으로 구분되어 주어진다. $(1 \leq H_i \leq 100)$

입력으로 주어지는 수는 모두 정수이다.

출력

첫째 줄에 게임에서 승리할 수 있는 경우의 수를 998ドル,244円,353円$로 나눈 나머지를 출력한다.

제한

힌트