13249번 - 공의 충돌 스페셜 저지

무게가 모두 같고, 크기가 0인 공 N개가 일직선 위에 놓여져 있다.

오른쪽으로 굴러가는 공과 왼쪽으로 굴러가는 공이 같은 속도로 충돌하면, 속도는 변하지 않고 공의 진행 방향만 바뀌게 된다.

공 N개의 위치가 주어진다. 효빈이는 공 N개의 진행 방향(오른쪽, 왼쪽)을 같은 확률로 결정한다. 시간 0일 때, 효빈이는 공을 결정한 방향으로 동시에 1초에 1만큼 이동하는 속도로 굴린다.

T초 후에 공이 충돌한 횟수의 기댓값을 구하는 프로그램을 작성하시오. (T초에 충돌한 것도 포함해야 한다)

첫째 줄에 공의 개수 N이 주어진다. (1 ≤ N ≤ 12)

둘째 줄에 공의 위치 N개가 주어진다. (0 ≤ 위치 ≤ 100,000,000, 위치는 정수) 공의 위치는 중복되지 않는다.

셋째 줄에 T (1 ≤ T ≤ 100,000,000)가 주어진다.

T초 동안 공이 충돌한 횟수의 기댓값을 출력한다.