We have $k$ around $10^6 - 10^7$. I need to compute value of the sum
$ S(k)=\sum_{n=0}^{\lfloor k/2 \rfloor}\frac{(k-n)!}{(k-2n)!n!} $
modulo $2462$. It seems that if a term has factors $2,1231$ (i.e. factors of $2462$) I can simply drop it but are there other tricks I could deploy in computing the value?
This is a stuck point from an assignment I found on internet which I'm working on to (re-)learn C and gain some understanding on algorithms. I would prefer some pointers instead of a solution. I feel confident that the sum could be simplified and there is something on modulo algebra I could use but I can't spot what I should try next.