Lucky Days

Chef Ciel defined a sequence S as follows: S[1] = A S[2] = B S[i] = (X*S[i-1] + Y*S[i-2] + Z) mod P, for i >= 3 Ciel considers C is a lucky number, and the i-th day is a lucky day if and only if S[i] = C. Ciel's restaurant may have special events in a lucky day. By the way, your work is calculating the numbers of lucky days in intervals. That is, for each Q intervals [L[i], R[i]], you