Counting Generalized Fibonacci Sequences

Consider a generalized Fibonacci sequence \(\{a_n\}\) defined by the recurrence

[ a_n = a_{n-1} + a_{n-2} \quad \text{for } n \ge 3, ]

with arbitrary real numbers \(a_1\) and \(a_2\). In this problem, you are given a fixed value \(a_1 = i\) and the second term \(a_2\) is an integer chosen from the interval \([l,r]\). For a given index \(k\) and integers \(p\) and \(m\), you are required to count the number of such sequences for which

[ a_k \bmod p = m. ]

Note: The sequence is uniquely determined by the choice of \(a_2\). When \(k \ge 3\), using the property of Fibonacci numbers with \(F_1=1\) and \(F_2=1\), we have

[ a_k = F_{k-2}\cdot a_1 + F_{k-1}\cdot a_2, ]

and hence the condition becomes

[ F_{k-1}\cdot a_2 + F_{k-2}\cdot i \equiv m \pmod{p}. ]

For the special cases when \(k=1\) or \(k=2\), the condition applies directly to \(a_1\) and \(a_2\) respectively.

inputFormat

The input consists of a single line containing six integers separated by spaces:

• i: the fixed value for \(a_1\)
• l and r: the lower and upper bounds for \(a_2\) (\(a_2\) is an integer in \([l, r]\))
• k: the index of the term to check
• p: the modulus
• m: the target remainder

All values fit in a 32-bit signed integer.

outputFormat

Output a single integer: the count of integers \(a_2\) in the interval \([l, r]\) that produce a generalized Fibonacci sequence (with \(a_1 = i\)) satisfying \(a_k \bmod p = m\).

sample

5 1 10 1 7 5

10