준혁이는 길이 N의 아주 큰 벽을 지을 계획이다.

딱히 이유는 없고 재밌어 보여서 지으려고 한다.

벽은 길이 1 단위로 구간을 나누어 N개의 구간 각각마다 높이가 결정되는 히스토그램의 모양이다.

준혁이는 i번째 구간의 높이를 a_i로 할지 b_i로 할지 아직 고민 중이다. (a_i \neq b_i)

그래서 준혁이는 각 구간의 높이를 독립적으로 정한 총 2^N가지 경우의 벽을 상상하면서 행복한 나날을 보내고 있다.

그러다 문득, 곧 장마철이라는 사실을 깨달은 준혁이는 비가 오면 벽에 물이 고인다는 사실을 알게 되었다.

길이 10짜리 벽의 높이가 차례대로 4, 2, 1, 8, 6, 2, 7, 1, 2, 3일 때 그림과 같은 벽이 지어진다.

여기서 비가 오면 그림처럼 좌우로 빠져나갈 곳이 없는 자리에 빗물이 고이게 된다.

준혁이는 2차원 세상에 살고 있어서 앞 뒤로 물이 빠지지는 못한다.

벽에 고인 빗물의 양은 넓이로 셀 수 있으며 위 그림에서는 총 14만큼의 물이 차있다.

준혁이는 이제 2^N가지 방법으로 지은 벽 위로 비가 내리는 상상을 하고 있다.

모든 가능한 방법에서 고이는 빗물의 양의 합은 얼마나 될까?

경우의 수가 너무 많으니 10^9+7로 나눈 나머지를 출력하도록 하자.

장마철 timer 5s memory 1024MB

장마철 5s 1024MB