Update Prefix Sum Array
for i in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] = ( dp [ i ] + dp [ i - 1 ] ) % MOD NEW_LINE DEDENT for i in range ( len ( Q ) ) : NEW_LINE INDENT ans = dp [ Q [ i ] [ 1 ] ] - dp [ Q [ i ] [ 0 ] - 1 ] NEW_LINE if ( ans < 0 ) : NEW_LINE INDENT ans += MOD NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT