### PROBLEM LINK:

**Author:** TSEC CodeCell

### DIFFICULTY:

Medium

### PROBLEM:

Find the number of ways a group can be split into a combination or pairs and solo units mod 10^9 +7.

### EXPLANATION:

We must find ways N distinct people can form pairs out of which some can remain alone.

So the Nth person can stay alone (1 way to do that), or pair with someone from 1 to N-1.

Thus f(N)= 1* f(N-1) + N-1 * f(N-2)

The solution can be optimized by caching all the results in an array.

The precomputation of all results take O(N) time and O(1) for answering each test query.

### AUTHORâ€™S SOLUTIONS:

Authorâ€™s solution can be found here.