LowbieH has a positive sequence {\(S_i\)} of length \(n\), numbered from 1 to n. Now she gives you a number k, and asks you to calculate all \(t_j\), which represents the product of all elements in interval \([j,j+k-1](1<=j<=n-k+1)\).

For smaller input, \(S_i\) can be calculated as follow : \(S_1 = A, S_i = (S_{i-1} * B + C) \ mod \ D (2 <= i <= n)\)

For smaller output, you need just output the xor sum of all \(t_j\) module P.