No budget smart ID card
Statement
Goal
A small company without budget wants to give all their employees a smart ID card with N pins that can be used to check an employee ID when inserted in a machine.The company has no enough money to manufacture cards with a chip, but they've found a solution for creating different combinations by soldering groups of pins together.
Examples:
For 3 pins there are 5 possible combinations:
| | _ | _ | _
O | O | /O\ | /O\ | /O\
| | | | | \ \ | | \
| ____ | | | | \ \ | | \
O O | /O O\ | |O| O | O\ O\ | |O O\
| \____/ | \_/ | \_/ | \____/
For 4 pins there are 15 possible combinations:
| ____ | | _ | _
O O | /O O\ | O O | /O\ O | O /O\
| \____/ | | | | | | |
| | ____ | | | | | |
O O | O O | /O O\ | |O| O | O |O|
| | \____/ | \_/ | \_/
-------------------------------------------
_ | _ | _ | ____ | ____
/O\ O | O /O\ | /O\ O | /O O\ | /O O\
\ \ | / / | | \ | | / | \ |
\ \ | / / | | \ | | / | \ |
O\ O\ | /O /O | |O O\ | |O /O | O\ O|
\_/ | \_/ | \____/ | \_/ | \_/
-------------------------------------------
_ | ____ | ____ | _ _ | _ _
O /O\ | /O O\ | /O O\ | /O\/O\ | /O\/O\
/ | | | | | \____/ | | || | | \ \ /
/ | | | | | ____ | | || | | \ \
/O O| | |O O| | /O O\ | |O||O| | /O\ O\
\____/ | \____/ | \____/ | \_/\_/ | \_/\_/
* Solders connect 2 or more pins.
* A card has 0,1, or more than 1 diferent solders. Diferent solders on the same card never share pins.
* Diferent solders can overlap, like the last example from 4-pin diagram where pin 1 is soldered only to pin 4, and pin 2 is soldered only to pin 3.
They want you to know how many different combinations can be made with N pins.
Input
Line 1: An integer N for the number of pins
Output
Line 1: The count of diferent IDs that can be made with N pins
Constraints
3 ≤ N ≤ 14
Example
Input
3
Output
5
Tags
Mathematics, Dynamic programming
Difficulty
Hard
Test cases
Test 1 Test
Input
3
Output
5
Validator 1 Validator
Input
8
Output
4140
Test 2 Test
Input
4
Output
15
Validator 2 Validator
Input
9
Output
21147
Test 3 Test
Input
5
Output
52
Validator 3 Validator
Input
10
Output
115975
Test 4 Test
Input
6
Output
203
Validator 4 Validator
Input
11
Output
678570
Test 5 Test
Input
7
Output
877
Validator 5 Validator
Input
12
Output
4213597
Test 6 Test
Input
13
Output
27644437
Validator 6 Validator
Input
14
Output
190899322
Solution language
Solution
Stub generator input