Recenetly I was learning Berlekamp-Massey and applying it when our dp can be seen as a linear recurrence, if you don't know how it works, here is an simple description of it.(or a more detail description in this blog
description
but when I encounter this problem 506E — Mr. Kitayuta's Gift,