Count the Buildings
There are \(N=100\) buildings arranged in a row.
Each has a distinct integer height ranging from \(1\) to \(N\) inclusive.
If you look from the first building, you can see 56 buildings;
if you look from the last building, you can see 2 buildings.
As an explicit example, suppose there is a configuration of 5 buildings with heights 1, 3, 2, 5, 4.
If you look from the first building, you can see 3 buildings (with heights 1, 3, 5) respectively.
If you look from the last building, you can see 2 buildings (with heights 4, 5) respectively.
Let \(S\) be the number of possible configurations of buildings such that the above is true. What are the last three digits of \(S\)?
Assume that you can only see a building if all buildings in front of it are strictly lower than it.