Count Dice Sequences

A standard die produces an integer from 1 through 6. Count all nonempty ordered sequences of outcomes whose sum is target. Different orders count separately. Return the count modulo 1,000,000,007.

Implement dice_combinations(target).

Input

target: The required sum of all rolls.

Output

Return the number of sequences modulo 1,000,000,007.

Contraintes

1 ≤ target ≤ 1,000,000. Taking a count modulo 1,000,000,007 means returning its remainder after division by that number.

Exemples

Entrée :
target = 2

Sortie attendue :
expected = 2

Entrée :
long long target = 2;

Sortie attendue :
long long expected = 2;

Entrée :
long target = 2;

Sortie attendue :
long expected = 2;

Entrée :
target = 4

Sortie attendue :
expected = 8

Entrée :
long long target = 4;

Sortie attendue :
long long expected = 8;

Entrée :
long target = 4;

Sortie attendue :
long expected = 8;

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

• Dice Combinations — 1633