As mentioned in an earlier comment, you should explain the concept a bit better. At least the job of a forerunner must be explained.

I added the boundaries for k and s.

An interesting kata!
Although I think it would be helpful to add a condition that len(data) is small and you should not dig into mathematics

FYI, my $O(n\log p)$ solution passes in 6 to 9 seconds.

Multiplication and division of large integers is not $O(1)$ so your solution is not really linear. :)

My linear solution times out. What is the expected time complexity?

Oops... hope I fixed that

In random test, p is not always a prime number.

Thanks! Me like klutz)
Fixed it

What I meant is not flip the ref sol result with user sol in the assertion, because that will give Expected <ref sol> to equal <user sol> on error. That will be confusing for users of course.

Run the ref sol first and put the ref sol result into a variable. And then, run the user sol and match it with the ref sol result variable.

The tests should run the ref sol first or copy the array first before executing user solution.

Fixed it

Thanks a lot for the comments!

Now the answer is searched modulo a prime number.
So I can remove restriction for k < 30 and sift out the naive solution without volatile test.
And now the implementation of the module is an significant part of this kata