ZombieRPGDice

This problem has a non-standard time limit: 4 seconds.

This problem is about a specific way of rolling the dice in one franchise of tabletop RPG games.

Whenever the player attempts a non-trivial action, the action is evaluated as follows:

• The game master sets the target value T based on the player's skill.
• The game master gives the player some 6-sided dice to roll. Each die is either positive or negative.
• The player rolls all the dice.
• As long as there is a positive and a negative die with the same value, a pair of such dice is removed from the roll.
• At this point, if there is a positive die with value less than or equal to the target, the roll is a success, otherwise it is a failure.
• Each negative die that was not removed counts as a point of stress for the player. In this problem the points of stress do not matter and can be ignored.

For example, suppose the player had the target T = 5 and rolled P = 4 positive and N = 6 negative dice, getting the values {3, 6, 3, 6} on the positive dice and the values {2, 3, 1, 6, 3, 3} on the negative dice. To evaluate this roll, we first remove several pairs of a positive and a negative die with the same value (value 3 twice and value 6 once). Once we do that, we now see {6} on the only remaining positive die and {2, 1, 3} on the three remaining negative dice. Thus, the roll is a failure and the player receives three points of stress.

You are given the target T, the number P of positive dice and the number N of negative dice. Calculate p: the probability that the roll will be a success. Return (p * 6^P+N) modulo 1,000,000,007.