String Transformation

Determine whether t is a rotation of s; if so, count the number of k-length sequences of nonzero suffix-rotations (moves that rotate s by l positions for 1 ≤ l ≤ n−1) whose combined rotation equals the shift mapping s to t, modulo 1e9+7 — otherwise return 0. The core challenge is counting k-tuples from Z_n\{0} whose sum equals the target shift under large constraints (n up to 5e5, k up to 1e15).