409443: GYM103561 H Carmen's Custom M&Ms

Carmen ended up falling asleep in the GDC the entire weekend, leaving her barely any time to shop for a Valentine's Day gift! Although she doesn't want to disappoint her significant other with a basic gift, she is really craving some chocolate to energize herself after a long nap. Carmen decides to order a jar of M&Ms, each one with a unique personalized design etched upon its surface (the idea being to say "awwww" then "ahhhh" as you consume them). Her plan for the date itself is then to play the following game in front of (yes not with) her significant other involving the M&Ms:

All of the M&Ms will initially be arranged in a single pile. While a pile still exists with at least two candies, Carmen picks one such pile to divide into two non-empty piles by choosing any nonempty subset of M&Ms to form a new pile. Given that Carmen has purchased $$$n$$$ M&Ms, she wonders how many possible different "games" she can play. Two piles of candies are considered the same if they contain the same set of candies. Two games are considered equal if Carmen makes the same sequence of choices and divides the piles in the same way.

The first and only line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$), indicating the number of M&Ms in the jar Carmen bought.

A single integer representing the number of possible games Carmen can play with her significant other modulo $$$10^9+7$$$ (the prime that signifies love of programming contests and UTPC).

3

3

4

18

For the first sample case, $$$N = 3$$$. Let the unique candies be designated by ABC. The $$$3$$$ possible games are decided by the very first move deciding what candy to isolate in its own pile (e.g. split into AB/C, AC/B, or BC/A).

For the second sample case, $$$N = 4$$$. Let the unique candies be designated by ABCD.

1: splitting into two piles AB and CD, dividing CD into C and D, and dividing AB into A and B

2: splitting into two piles AB and CD, dividing AB into A and B, and dividing CD into C and D

3: splitting into two piles ABD and C, dividing ABD into AD and B, and dividing AD into A and D

Action sequences 1, 2, and 3 are all considered unique games Carmen can play. 1 and 2 are different because the order of dividing up the smaller piles is switched. 1 and 2 are different from 3 because the first action divides the initial pile into different piles.