All aboard the factorial train The system

Assume the Earth is flat and that it extends infinitely in all directions. Now assume we have one infinitely long train railway and n trains in that railway. All trains have different speeds and all trains are going in the same direction. When a faster train reaches a slower train, the two trains connect (becoming a single train) and the new train keeps going at the speed with which the slower train was going.

E.g., if we have two trains, one going at speed 1 and another at speed 9, the lines below "simulate" what would happen on the railway:

9               1
         9       1
                 11
                  11
                   11


whereas if the trains start in a different order, we'd have

1 9
 1         9
  1                 9
   1                          9
etc...


With that being said, given a train/position/speed configuration there comes a time when no more connections will be made and the number of trains on the railway stays constant.

Task

Given the number n of trains in the railway, your task is to compute the total number of trains there will be on the railway, after all the connections have been made, summing over all n! possible arrangements of the n trains.

A possible algorithm would be:


Start counter at 0
Go over all possible permutations of the train speeds


Simulate all the connections for this permutation
Add the total number of remaining trains to the counter

Return the counter


Note that you can assume the train speeds are whatever n distinct numbers that you see fit, what really matters is the relationships between train speeds, not the magnitudes of the differences in speeds.

Input

You must take n, a positive integer, as input.

Output

An integer representing the total number of trains that there will be on the railway, summed over all possible permutations of the trains.

Test cases

1 -&gt; 1
2 -&gt; 3
3 -&gt; 11
4 -&gt; 50
5 -&gt; 274
6 -&gt; 1764
7 -&gt; 13068
8 -&gt; 109584
9 -&gt; 1026576
10 -&gt; 10628640
11 -&gt; 120543840
12 -&gt; 1486442880
13 -&gt; 19802759040
14 -&gt; 283465647360
15 -&gt; 4339163001600
16 -&gt; 70734282393600
17 -&gt; 1223405590579200
18 -&gt; 22376988058521600
19 -&gt; 431565146817638400
20 -&gt; 8752948036761600000




This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it! If you dislike this challenge, please give me your feedback. Happy golfing!
Jelly, &nbsp;5&nbsp; 4 bytes

!:RS


Try it online! Or see the test-suite.

How?

When we introduce an \$n^{\text{th}}\$ train it allows:


\$(n-1)!\$ states - by being placed behind none of the \$n-1\$ existing trains and being faster than all of them.
all the previous end states, each in \$n\$ different ways - by being placed behind at least one existing train and being faster than \$[0,n-1]\$ of the \$n-1\$ existing trains


We know \$a(1) = 1\$ so...  

n  a(n) 
1  1
2  1! + 1*2
3  2! + 1!*3 + 1*2*3
4  3! + 2!*4 + 1!*3*4 + 1*2*3*4
5  4! + 3!*5 + 2!*4*5 + 1!*3*4*5 + 1*2*3*4*5
... etc


Which is:

n  a(n) 
1  1
2  1 + 2
3  1*2 + 1* 3 + 2*3
4  1*2*3 + 1*2* 4 + 1* 3*4 + 2*3*4
5  1*2*3*4 + 1*2*3* 5 + 1*2* 4*5 + 1* 3*4*5 + 2*3*4*5
...
n  n!/n + n!/(n-1) + n!/(n-2) + ... + n!/1


Hence the code:

!:RS - integer, n
!    - (n) factorial      n!
  R  - range (n)          [1,...,n-2,n-1,n]
 :   - integer division   [n!/1,...,n!/(n-2),n!/(n-1),n!/n]
   S - sum                a(n)