Dice Throws Problem Statement

You are given D dice, each having F faces numbered from 1 to F. The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up numbers equals the given 'target' sum S.

Example:

Input:

2
3 6 8
2 4 5

Output:

21
4

Explanation:

In the first test case, there are 3 dice each with 6 faces and the possible ways to roll them to get a sum of 8 are 21. In the second test case, there are 2 dice each with 4 faces, and there are 4 ways to roll them to reach the sum of 5.

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ D, F ≤ 50
• 1 ≤ S ≤ 10^3

Note:

As the result can be large, return your answer modulo 10^9 + 7.

Follow Up:

Can you optimize the solution to use no more than O(S) extra space?