Firstly it is clear that we must somehow find a formula for S as 3^37 is much too massive. Secondly the problem seems to be working with numbers mod 4, so I tried to incorporate that into my thinking.
The first thing I wanted to do is understand f, so we re-write it as such;
My next goal is to find a formula for S(4n + 3), I derive some identities with f(4n + 3), f(4n + 2), f(4n + 1), and f(4n).
Using 4 we can generate the required recurrence,
However a minor correction needs to be made,
And voila we now have a recurrence relation which is simple to implement, but it still takes a while so we need to cache the data, otherwise it will never finish running, luckily I have just learnt about python Decorators, specifically the cache decorator which I found from this video, essentially this is an inbuilt memoization function! It is extremely useful and I have been waiting for an opportunity to use this.
Enter 2 integers (base, pow)
Code will output S(base^pow) % 10^9