하늘에서 떨어지는 $\infty$개의 별

당신은 $D$일 동안 하떨별 마을의 환경 관리자로 일하게 되었다. 하떨별 마을은 하늘에서 별이 떨어지기로 유명한 마을로 별들은 다음과 같은 규칙으로 떨어진다.

• 별이 떨어지는 위치는 $\infty$개의 점이다. 점은 순서대로 $1$, $2$, $3$, $\cdots$의 번호를 갖는다.
• 첫날 낮에 모든 점에 쌓인 별의 개수는 각각 $0$개다.
• $i$번 점에는 매일 밤 $s_i$개의 별이 떨어진다. $s_0$, $X$, $M$는 상수이며, $s_{i+1}=(s_{i} + X) \bmod M$이다.

별이 많이 쌓이면 폭발할 수 있기 때문에 쌓인 별을 청소해야 한다.

• 임의의 $i$번 점에 쌓인 별의 개수가 $K$개를 초과하면 해당 점의 별들이 폭발한다.
• 별이 떨어지는 밤이 되기 전, 낮에 청소 작업을 할 수 있다. 청소 작업을 진행하면 모든 점에 쌓인 별이 $0$개가 된다.

여러분은 $D$일 동안 떨어진 별이 폭발하지 않게 관리해야 한다. $D$일 동안 별이 폭발하지 않도록 하는 최소 청소 횟수를 구해보자.

첫 번째 줄에 정수 $s_0$, $X$, $M$, $D$, $K$가 공백으로 구분되어 주어진다.

첫 번째 줄에 $D$일 동안 별이 폭발하지 않도록 할 수 있는 최소 청소 횟수를 출력한다.

• $1 \le X, D, K \le 10^{18}$
• $1 \le M \le K$
• $0 \le s_0 \lt M$