Help me in solving DEVLOCK problem

help
,
1

My issue

Any solution idea for this problem Devu and Locks?

I have a solution with Digit DP in which I required a 1e9 order DP array which is impossible I know -.-

Is there any solution that can take less space?

How can use FFT or Mat Expo stuff for this problem?

Thanks in advance!!

Problem Link: Devu and Locks Practice Coding Problem