static int calculate ( int pos , int rem , int z , int k , int n ) {
  if ( rem == 0 && z != 0 ) {
    if ( pos != n ) return ( powers [ n - pos - 1 ] * 9 ) % mod ;
    else return 1 ;
  }
  if ( pos == n ) return 0 ;
  if ( dp [ pos ] [ rem ] [ z ] != - 1 ) return dp [ pos ] [ rem ] [ z ] ;
  int count = 0 ;
  for ( int i = 0 ;
  i < 10 ;
  i ++ ) {
    if ( i == 0 ) count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , z , k , n ) ) ) % mod ;
    else count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , 1 , k , n ) ) ) % mod ;
  }
  return dp [ pos ] [ rem ] [ z ] = count ;
}

static int calculate ( int pos , int rem , int z , int k , int n ) { if ( rem == 0 && z != 0 ) { if ( pos != n ) return ( powers [ n - pos - 1 ] * 9 ) % mod ; else return 1 ; } if ( pos == n ) return 0 ; if ( dp [ pos ] [ rem ] [ z ] != - 1 ) return dp [ pos ] [ rem ] [ z ] ; int count = 0 ; for ( int i = 0 ; i < 10 ; i ++ ) { if ( i == 0 ) count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , z , k , n ) ) ) % mod ; else count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , 1 , k , n ) ) ) % mod ; } return dp [ pos ] [ rem ] [ z ] = count ; }
(method_declaration (modifiers) type: (integral_type) name: (identifier) parameters: (formal_parameters (formal_parameter type: (integral_type) name: (identifier)) (formal_parameter type: (integral_type) name: (identifier)) (formal_parameter type: (integral_type) name: (identifier)) (formal_parameter type: (integral_type) name: (identifier)) (formal_parameter type: (integral_type) name: (identifier))) body: (block (if_statement condition: (parenthesized_expression (binary_expression left: (binary_expression left: (identifier) right: (decimal_integer_literal)) right: (binary_expression left: (identifier) right: (decimal_integer_literal)))) consequence: (block (if_statement condition: (parenthesized_expression (binary_expression left: (identifier) right: (identifier))) consequence: (return_statement (binary_expression left: (parenthesized_expression (binary_expression left: (array_access array: (identifier) index: (binary_expression left: (binary_expression left: (identifier) right: (identifier)) right: (decimal_integer_literal))) right: (decimal_integer_literal))) right: (identifier))) alternative: (return_statement (decimal_integer_literal))))) (if_statement condition: (parenthesized_expression (binary_expression left: (identifier) right: (identifier))) consequence: (return_statement (decimal_integer_literal))) (if_statement condition: (parenthesized_expression (binary_expression left: (array_access array: (array_access array: (array_access array: (identifier) index: (identifier)) index: (identifier)) index: (identifier)) right: (unary_expression operand: (decimal_integer_literal)))) consequence: (return_statement (array_access array: (array_access array: (array_access array: (identifier) index: (identifier)) index: (identifier)) index: (identifier)))) (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (decimal_integer_literal))) (for_statement init: (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (decimal_integer_literal))) condition: (binary_expression left: (identifier) right: (decimal_integer_literal)) update: (update_expression (identifier)) body: (block (if_statement condition: (parenthesized_expression (binary_expression left: (identifier) right: (decimal_integer_literal))) consequence: (expression_statement (assignment_expression left: (identifier) right: (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (parenthesized_expression (method_invocation name: (identifier) arguments: (argument_list (binary_expression left: (identifier) right: (decimal_integer_literal)) (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (array_access array: (identifier) index: (identifier)))) right: (identifier)))) right: (identifier)) (identifier) (identifier) (identifier)))))) right: (identifier)))) alternative: (expression_statement (assignment_expression left: (identifier) right: (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (parenthesized_expression (method_invocation name: (identifier) arguments: (argument_list (binary_expression left: (identifier) right: (decimal_integer_literal)) (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (array_access array: (identifier) index: (identifier)))) right: (identifier)))) right: (identifier)) (decimal_integer_literal) (identifier) (identifier)))))) right: (identifier))))))) (return_statement (assignment_expression left: (array_access array: (array_access array: (array_access array: (identifier) index: (identifier)) index: (identifier)) index: (identifier)) right: (identifier)))))