30989번 - 다항함수의 미분과 나머지

문제

6ドル$개의 정수 $n,ドル $d,ドル $m,ドル $k,ドル $a,ドル $b$와 정수열 $s=(s_0, s_1, \cdots, s_d)$가 주어진다.

다음을 모두 만족하는 모든 정수열 $c=(c_0, c_1, \cdots, c_n)$들의 집합을 $A$라 하자.

• 모든 정수 $i$ (0ドル \le i \le n$)에 대해 $a \le c_i \le b$
• 다음을 모두 만족하는 함수 $f \colon \mathbb R \to \mathbb R$와 정수열 $r=(r_0, r_1, \cdots, r_d)$가 존재한다.
  • 모든 실수 $t$에 대해 $f(t) = \sum_{i=0}^{n} c_i t^i$
  • 모든 실수 $t$에 대해 $f^{(k)}(t) = \sum_{j=0}^{d} r_j t^j$
  • 모든 정수 $j$ (0ドル \le j \le d$)에 대해 $r_j \bmod m = s_j$

집합 $A$의 크기와 $A$의 원소 중 사전 순으로 가장 작은 원소를 구해 보자.

입력

첫 번째 줄에 6ドル$개의 정수 $n,ドル $d,ドル $m,ドル $k,ドル $a,ドル $b$가 공백으로 구분되어 주어진다.

두 번째 줄에 $d+1$개의 정수 $s_0,ドル $s_1,ドル $\cdots,ドル $s_d$가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 $|A| \bmod (10^9+7)$의 값을 출력한다.

만약 $A$가 공집합이 아니라면, $A$에 속하는 정수열 중 사전 순으로 가장 작은 것을 $p$라 할 때, 두 번째 줄에 $n+1$개의 정수 $p_0,ドル $p_1,ドル $\cdots,ドル $p_n$을 공백으로 구분하여 출력한다.

제한

• 0ドル \le n \le 10^5$
• 0ドル \le d \le 10^5$
• 1ドル \le m \le 10^9$
• 0ドル \le k \le 10^9$
• 0ドル \le a \le b \le 10^9$
• 모든 정수 $j$ (0ドル \le j \le d$)에 대해 0ドル \le s_j < m$

노트

• $f^{(k)}$는 함수 $f$를 $k$번 미분해서 얻은 함수이다.
  • $f^{(0)} = f$
  • 모든 양의 정수 $k$에 대해 $f^{(k)} = (f^{(k-1)})'$
• 모든 실수 $x$에 대해 $x^0=1$로 본다.
• $\mathbb R$는 실수 전체의 집합이다.
• $x \bmod y$는 $x$를 $y$로 나눈 나머지이다.
• $|A|$는 집합 $A$의 크기이다.
• 정수열 $x=(x_0, x_1, \cdots, x_l)$가 정수열 $y=(y_0, y_1, \cdots, y_l)$보다 사전 순으로 작다는 것은 다음을 모두 만족하는 정수 $h$ (0ドル \le h \le l$)가 존재한다는 의미이다.
  • $x_h < y_h$
  • 모든 정수 $i$ (0ドル \le i < h$)에 대해 $x_i=y_i$