2000720 - 幸运数

周周认为在 a 到 b 之间(包括 a 和 b)且是 k 的倍数的数是幸运数,玩仔拿着一个数 n 问周周是不是幸运数,请你帮周周回答玩仔。

Input

输入第一行包含三个正整数 a, b, k(1 \leq a, b, k \leq 10^9, a \leq b) 。

第二行包含一个正整数 n(1 \leq n \leq 10^9) 。

Output

输出一行,是幸运数输出1,否则输出0。

Examples

Input

1 5 2
4

Output

1

Input

7 10 3
6

Output

0
Time Limit 1 second
Memory Limit 128 MB
Discuss 题解 Stats
上一题 下一题