# 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.

×