text: /**
  1155. Number of Dice Rolls With Target Sum
  
  You have d dice, and each die has f faces numbered 1, 2, ..., f.
  
  Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.
  
   
  
  Example 1:
  
  Input: d = 1, f = 6, target = 3
  Output: 1
  Explanation: 
  You throw one die with 6 faces.  There is only one way to get a sum of 3.
  Example 2:
  
  Input: d = 2, f = 6, target = 7
  Output: 6
  Explanation: 
  You throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:
  1+6, 2+5, 3+4, 4+3, 5+2, 6+1.
  Example 3:
  
  Input: d = 2, f = 5, target = 10
  Output: 1
  Explanation: 
  You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.
  Example 4:
  
  Input: d = 1, f = 2, target = 3
  Output: 0
  Explanation: 
  You throw one die with 2 faces.  There is no way to get a sum of 3.
  Example 5:
  
  Input: d = 30, f = 30, target = 500
  Output: 222616187
  Explanation: 
  The answer must be returned modulo 10^9 + 7.
   
  
  Constraints:
  
  1 <= d, f <= 30
  1 <= target <= 1000
   */
  
  /**
   * @param {number} d
   * @param {number} f
   * @param {number} target
   * @return {number}
   */
  var numRollsToTarget = function(d, f, target) {
      const cache = {};
      const modulo = (10**9 + 7);
      const helper = (die, faces, tar) => {
          let ret = 0;
          const str =  `${die}_${faces}_${tar}`;
          if ( str in cache ) {
              return cache[str]
          }
          
          if ( die <= 0 || tar <= 0 ) {
              cache[str] = 0;
              return ret;
          }
          if ( faces * die < tar ) {
              cache[str] = 0;
              return ret;
          }
          if ( die === 1 && faces >= tar ) {
              cache[str] = 1;
              return 1;
          }
          
          for ( let i = 1 ; i <= faces ; i++ ) {
              ret = ( ret + helper( die-1, faces, tar-i ) ) % modulo;
          }
          cache[ str ] = ret;
          return ret;   
      }
      return helper( d, f, target );
  };
  
  /**
  1
  6
  3
  2
  6
  7
  2
  5
  10
  1
  2
  3
  30
  30
  500
   */