# Đề thi Bắc Giang PreVOI 2023 - Ngày thi thứ nhất

---

# RECS
Gia Huy muốn mua một mảnh đất hình chữ nhật và xây dựng ba tòa nhà trên mảnh đất đó.

Các tòa nhà phải là hình chữ nhật có kích thước $a_1 \times b_1, a_2 \times b_2$ và $a_3 \times b_3$. Các tòa nhà có thể chạm vào nhau nhưng không được chồng lên nhau. Chúng cũng có thể được xoay miễn là các cạnh song song với trục tọa độ.

Tính diện tích đất Gia Huy cần mua?
## Input
- Dòng đất tiên ghi số lượng test $t$ $(1 \le t \le 1000)$.
- Sau đó là $t$ dòng, mỗi dòng ghi $6$ số nguyên $a_1, b_1, a_2, b_2, a_3$ và $b_3$ $(1 \le a_1, b_1,a_2,b_2,a_3,b_3 \le 10^9)$.
## Output
Đối với mỗi test, in ra diện tích đất tối thiểu Gia Huy cần mua để có thể xây dựng ba tòa nhà.

## Sample Test
**Input**

2
2 3 2 2 1 1
2 4 5 1 2 3

**Output**

12
21

---

# CHAMELEON

Đất nước Sanguinesia là nơi sinh sống của hàng chục loài tắc kè hoa khác nhau. Nhân dịp sinh nhật, bạn Khoa quyết định tự thưởng cho mình một chuyến đi đến đất nước này để được tận mắt nhìn thấy những con tắc kè hoa sặc sỡ và dễ thương!

Đất nước Sanguinesia có $N$ thành phố khác nhau, đất số từ $1$ đến $N$. Có $M$ con đường $2$ chiều, mỗi con đường nối $2$ thành phố khác nhau. Đối với $2$ thành phố bất kì, có nhiều nhất một con đường nối giữa chúng. Các thành phố đều liên thông với nhau, có nghĩa là từ một thành phố bất kì, luôn tồn tại một tuyến đường để đến các thành phố còn lại.

Bạn Khoa sẽ bắt đầu chuyến đi của mình ở thành phố $X$, và bạn ấy sẽ kết thúc chuyến đi của mình ở một thành phố $Y$ có chỉ số lớn hơn $X$. Có thể có nhiều cách để di chuyển từ thành phố $X$ đến thành phố $Y$. Vì vậy, trước khi lên đường, bạn ấy cần biết trước những con đường và thành phố nào là tất yếu cho chuyến đi của bạn.

Một con đường được gọi là tất yếu giữa thành phố $X$ và thành phố $Y$ khi mọi tuyến đường từ thành phố $X$ đến thành phố $Y$ đều bắt buộc phải đi qua con đường đó. Nói cách khác, nếu con đường đó bị bỏ đi, thì không còn đường đi nào từ thành phố $X$ đến thành phố $Y$ nữa. Bạn Khoa đặt $F(X,Y)$ là số lượng con đường tất yếu giữa thành phố $X$ và thành phố $Y$.

Tương tự vậy, một thành phố được gọi là tất yếu giữa thành phố $X$ và thành phố $Y$ khi mọi tuyến đường từ thành phố $X$ đến thành phố $Y$ đều bắt buộc phải đi qua thành phố đó. Bạn Khoa đặt $G(X,Y)$ là số lượng thành phố tất yếu giữa thành phố $X$ và thành phố $Y$. Lưu ý theo định nghĩa này, thành phố $X$ và thành phố $Y$ đều được coi là thành phố tất yếu.

Cuối cùng, bạn Khoa gọi $H(X,Y)$ là độ vui của chuyến đi. Độ vui của chuyến đi được tính theo công thức sau:

$H(X,Y)=(F(X,Y) \times A + G(X,Y) \times B)^C$

trong đó, $A,B$ và $C$ là những hằng số cố định cho trước.

Bạn Khoa chưa quyết định được thành phố $X$ và thành phố $Y$ sẽ là hai thành phố nào. Là con người tò mò, bạn muốn biết tổng độ vui của tất cả các chuyến đi có thể diễn ra. Hãy giúp Khoa.

Cụ thể hơn, hãy tính tổng của $H(X,Y)$ với mọi cặp số $(X,Y)$ thỏa mãn $1 \le X < Y \le N$. Vì tổng này có thể rất lớn, nên hãy in ra phần dư của tổng đó khi chia cho số $(10^9 + 7)$.

## Input
- Dòng đầu tiên ghi $5$ số nguyên $N,M,A,B,C$ $(2 \le N \le 10^5$, $N - 1 \le M \le min(N \times (N-1)$ $÷$ $2, 2 \times 10^5)$, $0 \le A,B \le 10^9$, $1 \le C \le 2)$.
- Dòng thứ $i$ trong $M$ dòng tiếp theo ghi $2$ số nguyên $u_i$ và $v_i$ $(1 \le u_i, v_i \le N$, $u_i \neq v_i)$ là chỉ số của hai thành phố được nối bởi con đường thứ $i$.
- Dữ liệu đảm bảo cách bố trí các con đường thỏa mãn điều kiện đề bài.

## Output
In ra đáp án của bài toán theo module $(10^9 + 7)$.

## Sample Test
**Input**

4 3 10 12 2
1 2
2 3
3 4

**Output**

15824

**Giải thích**

Giá trị của $F(X,Y)$, $G(X,Y)$ và $H(X,Y)$ như sau:
- $F(1,2) = 1, G(1,2) = 2, H(1,2) = (1 \times 10 + 2 \times 12)^2=1156$.
- $F(1,3) = 2, G(1,3) = 3, H(1,3) = (2 \times 10 + 3 \times 12)^2=3136$.
- $F(1,4) = 3, G(1,4) = 4, H(1,4) = (3 \times 10 + 4 \times 12)^2=6084$.
- $F(2,3) = 1, G(2,3) = 2, H(2,3) = (1 \times 10 + 2 \times 12)^2=1156$.
- $F(2,4) = 2, G(2,4) = 3, H(2,4) = (2 \times 10 + 3 \times 12)^2=3136$.
- $F(3,4) = 1, G(3,4) = 2, H(3,4) = (1 \times 10 + 2 \times 12)^2=1156$.

Tổng của $H(X,Y)$ là $1156+3136+6084+1156+3136+1156=15824$.

## Scoring
- Subtask 1 $(20\%)$: $2 \le N \le 100$.
- Subtask 2 $(10\%)$: $A = 0$ và $C = 1$.
- Subtask 3 $(20\%)$: $A = 0$ và $C = 2$.
- Subtask 4 $(10\%)$: $B = 0$ và $C = 1$.
- Subtask 5 $(20\%)$: $B = 0$ và $C = 2$.
- Subtask 6 $(20\%)$: Không có ràng buộc gì thêm.

---

# MONEY
Nhật là một đại gia với lượng tài sản khổng lồ. Nhật không thể mang theo toàn bộ số tiền của mình, nên hôm nay Nhật chỉ mang $N$ mệnh giá khác nhau, bao gồm $10^{100}$ tờ tiền có mệnh giá $a_1$ đồng, $10^{100}$ tờ tiền có mệnh giá $a_2$ đồng, $\dots$, $10^{100}$ tờ tiền có mệnh giá $a_N$ đồng.

Nhật muốn mua một mảnh đất có giá trị là $K$. Với số tiền mà Nhật mang đi hôm nay, hãy tính số cách Nhật có thể mua mảnh đất.

Hai cách mua được coi là khác nhau nếu tồn tại một mệnh giá mà một cách mua sử dụng nhiều hoặc ít tờ tiền hơn cách mua còn lại.

Do số cách mua có thể rất lớn, hãy in số cách mua theo module $10^9+7$.

## Input
- Dòng đầu tiên ghi hai số nguyên $N, K$ $(1 \le 5000, 1 \le K \le 10^{18})$.
- Dòng tiếp theo gồm $N$ số nguyên phân biệt $a_1, a_2, \dots, a_N$ $(1 \le a_i \le K)$.

## Output
In ra đáp án của bài toán theo module $(10^9 + 7)$.

## Sample Test
**Input**

3 6
1 2 3

**Output**

7

**Giải thích**

Có $7$ cách mua như sau:
- Dùng $2$ tờ tiền $3$ đồng.
- Dùng $1$ tờ tiền $3$ đồng, $1$ tờ tiền $2$ đồng và $1$ tờ tiền $1$ đồng.
- Dùng $1$ tờ tiền $3$ đồng và $3$ tờ tiền $1$ đồng.
- Dùng $2$ tờ tiền $2$ đồng và $2$ tờ tiền $1$ đồng.
- Dùng $1$ tờ tiền $2$ đồng và $4$ tờ tiền $1$ đồng.
- Dùng $3$ tờ tiền $2$ đồng.
- Dùng $6$ tờ tiền $1$ đồng.

## Scoring

Với $S = \sum_{i=1}^N a_i$.
- Subtask 1 $(10\%)$: $1 \le N, K \le 10$.
- Subtask 2 $(40\%)$: $1 \le N, K \le 5000$.
- Subtask 3 $(10\%)$: $N = 2$ và $1 \le K \le 10^9$.
- Subtask 4 $(40\%)$: $S \le 100$.