Update Prefix Sum Array
for ( int i = 1 ; i < N ; i ++ ) { dp [ i ] = ( dp [ i ] + dp [ i - 1 ] ) % MOD ; } for ( int i = 0 ; i < Q . size ( ) ; i ++ ) { long int ans = dp [ Q [ i ] [ 1 ] ] - dp [ Q [ i ] [ 0 ] - 1 ] ; if ( ans < 0 ) ans = ans + MOD ; cout << ans << endl ; } }