cho.shHyperrectangle
상자에서 좌표의 합이 s 이하인 부분의 부피에 d!을 곱한 값을 1e9+7로 나눈 나머지를 구한다.
어려움9조합론수학동적 계획법기하아직 제출이 없습니다시간 제한2초메모리 제한512 MB문제 설명
예제2
문제
Snuke received a d-dimensional hyperrectangle of size l1 × · · · × ld as a birthday present. Snuke placed it such that its i-th coordinate becomes between 0 and li, and ate the part of the hyperrectangle that satisfies x1 + · · · + xd ≤ s. (Here xi denotes the i-th coordinate). Let V be the volume of the part eaten by Snuke. We can prove that d!V (V times the factorial of d) is always an integer. Compute d!V modulo 109 + 7.
입력
First line of the input file contains one integer d (2 ≤ d ≤ 300). Then d lines follow; i-th of these lines contain one integer li (1 ≤ li ≤ 300). Last line contains one integer s (0 ≤ s ≤ Σli).
출력
Print d!V modulo 109 + 7.
힌트
Illustration to Sample 1:
