보석괴물의 몸에는 0부터 9사이의 숫자가 적혀 있다고 한다.

보석괴물이 사라지기 전에 보석 괴물의 몸통 구간에 새겨진 숫자의 합과 몸통 구간의 길이가 일치하는 모든 경우의 수를 정확하게 말한다면 소원을 이루어주고 사라진다고 한다.

몸통 길이를 n이라고 할 때 그 범위는 다음과 같다. (1 ≤ n ≤ 100\ 000)

a_l, a_{l+1}, a_{l+2}, \cdots , a_{r-1}, a_r의 몸통구간이 있을 때, 이 몸통 구간의 합과 구간의 길이가 일치하는 모든 경우의 수를 구하여라 ! (l \le r)

보석 괴물 timer 1s memory 128MB

보석 괴물 1s 128MB