총 \mathbf{N}장의 팬케이크를 굽는다. 반지름이 1센티미터(cm)인 팬케이크를 하나, 반지름이 2cm인 팬케이크를 하나, 반지름이 3cm인 팬케이크를 하나, ..., 반지름이 \mathbf{N}cm인 팬케이크를 하나 굽는데, 굽는 순서는 임의일 수 있다. 첫 번째 팬케이크를 구운 뒤에는 접시에 올려 둔다. 그 다음부터는 팬케이크를 하나 구울 때마다, 바로 직전에 만든 팬케이크 위에 중심을 맞춰 포개어 올린다. 이때 새로 올린 팬케이크는 올리는 순간에는 위에서 보인다. 어떤 팬케이크가 가려져 보이지 않게 되는 것은, 나중에 더 큰 반지름의 팬케이크를 위에 올렸을 때뿐이다.

예를 들어 4장의 팬케이크를 굽는다고 하자. 먼저 반지름이 3cm인 팬케이크를 굽는데, 이는 보인다. 그 다음 반지름이 1cm인 팬케이크를 구워 위에 올리면 둘 다 보인다. 세 번째로 반지름이 2cm인 팬케이크를 구워 올리면, 이는 바로 아래의 팬케이크(반지름 1)를 가리지만 첫 번째 팬케이크(반지름 3)는 가리지 못하므로 총 2장이 보이는 상태가 된다. 마지막으로 반지름이 4cm인 팬케이크를 구워 올리면 다른 모든 팬케이크를 가려서 1장만 보이게 된다. 아래 그림은 각 팬케이크를 구운 뒤의 스택 상태를 보여준다. 각 스택에서 완전히 색칠된 팬케이크는 보이는 것이고, 반투명한 팬케이크는 보이지 않는 것이다.

Four stacks with pancakes of radii 3, 3 and 1, 3, 1 and 2, and 3, 1, 2 and 4.

스택에 정확히 i장의 팬케이크가 있을 때 위에서 보이는 팬케이크의 수를 \mathbf{V_i}라고 하자. 위 예시에서는 \mathbf{V_1} = 1, \mathbf{V_2} = 2, \mathbf{V_3} = 2, \mathbf{V_4} = 1이다.

\mathbf{V_1}, \mathbf{V_2}, \dots, \mathbf{V_N}이 주어질 때, 가능한 \mathbf{N}!개의 굽는 순서 중에서 이 값들을 만들어내는 순서는 몇 개인가? 출력 값이 매우 커질 수 있으므로, 결과를 소수 10^9+7(1000000007)로 나눈 나머지만 출력하라.

#10406 upload 1 done 1 how_to_reg 1

Hidden Pancakes timer 30s memory 1024MB

#10406

Hidden Pancakes 30s 1024MB