Kì này Trung đã đăng ký học xác suất thống kê, do cậu đi học đầy đủ nên cậu cũng không sợ bài kiểm tra giữa kỳ lắm. Biết rằng môn xác suất thống kê sẽ lấy điểm trung bình của ~5~ bài kiểm tra, làm tròn lên. Với mỗi bài kiểm tra thứ ~i~ (~1 \le i \le 5~), khả năng cậu được ~j~ điểm ~(j \in \mathbb{N}, 0 \le j \le 10)~ là ~p_{ij}~ (đơn vị %). Với mỗi điểm trung bình ~x~ ~(x \in \mathbb{N}, 0 \le x \le 10 )~, hãy tính khả năng Trung đạt được điểm ~x~.

Input

Gồm ~5~ dòng, dòng thứ ~i~ mỗi dòng chứa 11 số nguyên không âm ~p_{ij}~ (~\forall i:~ ~\sum_{j=0}^{10} p_{ij} = 100~).

Output

Xuất ra một dòng duy nhất gồm 11 số thực, số thứ ~i (0 \le i \le 10)~ là tỉ lệ (đơn vị %) Trung đạt được điểm trung bình ~i~ . Kết quả xuất ra được coi là đúng nếu chênh lệch với đáp án không quá ~10^{-9}~.

Sample Input 1

0 10 10 10 10 10 10 10 10 10 10
5 10 10 10 10 10 10 10 10 10 5
10 10 10 10 10 10 10 10 10 10 0
5 10 10 10 5 10 10 10 10 10 10
5 10 5 5 10 10 10 10 10 10 15

Sample Output 1

0.0000000000 0.0411250000 0.8383750000 4.9903750000 14.8588750000 25.8321250000 27.5681250000 17.9501250000 6.6836250000 1.1862500000 0.0510000000

Note

Cho dãy số gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~. Hãy đếm số cặp (~i~, ~j~) thỏa mãn:

• ~1 \le i < j \le n~.

• ~j - i > 5~.

• ~|a_i - a_j|~ chia hết cho ~23~.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~).

Dòng thứ hai gồm ~n~ số nguyên dương mô tả dãy số ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~, ~1 \le i \le n~).

Output

In ra một số nguyên duy nhất là số cặp (~i~, ~j~) thỏa mãn yêu cầu đề bài.

Scoring

Sample Input 1

10
1 24 25 4 30 15 3 1 24 2

Sample Output 1

5

Notes

Trong ví dụ, các cặp số (~i~, ~j~) thỏa mãn là:

1. (~1~, ~8~)

2. (~1~, ~9~)

3. (~2~, ~8~)

4. (~2~, ~9~)

5. (~3~, ~10~)

Vốn là một nhà nghiên cứu xuất chúng tại Bắc cực, Việt đã nghiên cứu được rằng các loài hải cẩu trắng trong tự nhiên phổ biến hơn cả. Tuy nhiên, Tài với sự yêu thích đặc biệt về hải cẩu đen của mình lại không đồng ý với điều này, và anh sẽ chứng minh rằng Việt đã sai bằng cách phá đàn hải cẩu của Việt.

Hiện tại Việt đang có một đàn hải cẩu gồm ~n~ con để nghiên cứu. Là một người sống khoa học, Việt đã sắp xếp lại các con hải cẩu theo thứ tự sao cho việc nghiên cứu của anh thuận tiện nhất. Để phá, sao cho khó bị Việt phát hiện, Tài sẽ chọn một đoạn liên tiếp các con hải cẩu bất kỳ trong đàn. Thay những con trắng bằng con đen và ngược lại trong đoạn đó. Nghĩ là thế nhưng anh chưa muốn làm thằng liều, vì Việt nổi tiếng rất khó tính. Vì thế Tài đang tưởng tượng trong đầu rằng: Trong tất cả các cách phá có thể của mình (kể cả khi không phá), số lượng số con hải cẩu đen khác nhau là bao nhiêu?

Input

Dòng đầu tiên là ~n~ (~1 \leq n \leq 2 \cdot 10^5~) cho biết số con hải cẩu trong đàn của Việt.

Dòng tiếp theo là một xâu nhị phân gồm ~n~ ký tự, ký tự ~0~ cho biết một con hải cẩu trắng và ~1~ cho biết một con hải cẩu đen.

Output

Ghi một số duy nhất cho biết số lượng số con hải cẩu đen khác nhau trong tất cả các cách phá.

Scoring

Sample Input 1

4
1101

Sample Output 1

4

Note

Có thể chọn đoạn ~[3, 3]~ để dãy trở thành 1111.

Cũng có thể chọn đoạn ~[2, 2]~ để dãy trở thành 1001.

Hoặc chọn đoạn ~[1, 2]~ để dãy trở thành 0001.

Không tồn tại cách nào tạo ra dãy 0000. Vậy ta có thể tạo ra được đàn hải cẩu có lần lượt ~1~, ~2~, ~3~ hoặc ~4~ con hải cẩu đen. Đáp án là ~4~.

~XXX~ là một nhà khai phá tài ba. Vào một ngày đẹp trời, ~XXX~ phát hiện một quần đảo gồm ~n~ hòn đảo nhỏ, được đánh số từ ~1~ đến ~n~. Bỗng nhiên, tại trung tâm của những hòn đảo lung linh xinh đẹp ấy, một vị thần đèn khổng lồ từ từ trồi lên khỏi mặt nước. Ngài tự xưng mình là ~YYY~, vị thần đèn vĩ đại nhất thế giới, sẽ ban cho ~XXX~ một thử thách khó nhằn cùng với phần thưởng vô cùng to lớn.

Thần đèn ~YYY~ ban đầu ban cho ~XXX~ một lượng lớn vàng ~D~ và bắt đầu thử thách sử dụng số vàng ấy. Sau khi hoàn thành xong thử thách, ~XXX~ có thể giữ lại lượng vàng còn lại.

Thử thách của ~YYY~ yêu cầu ~XXX~ xây dựng những cây cầu bằng vàng giữa những hòn đảo, giữa hòn đảo thứ ~i~ và thứ ~j~ nếu xây dựng cây cầu sẽ tốn ~c_{i, j}~ đơn vị vàng. Ngoài ra sau khi xây xong, quần đảo phải có những thuộc tính sau:

• Giữa ~2~ hòn đảo không có quá ~1~ cây cầu.

• Mỗi hòn đảo chỉ được kết nối với đúng 2 hoặc 0 hòn đảo khác thông qua những cây cầu vàng.

• Có ít nhất một hòn đảo được kết nối với đúng 2 hòn đảo khác thông qua những cây cầu vàng.

Hãy cho biết ~XXX~ có thể vượt qua thử thách của thần đèn hay không nhé! Nếu ~XXX~ có thể vượt qua thử thách của thần đèn, hãy cho biết số vàng lớn nhất mà ~XXX~ có thể nhận được là bao nhiêu.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ (~1 \le n~) và ~D~ (~0 \le D \le 10^{18}~) cho biết số lượng hòn đảo trong quần đảo và số lượng đơn vị vàng ban đầu được ban tặng.

Trong ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên dương, số ở dòng thứ ~i~ và cột thứ ~j~ gọi là ~c_{i, j}~ (~0 < c_{i, j} \le 10^9~) cho biết lượng vàng phải bỏ ra khi xây dựng cầu giữa hòn đảo thứ ~i~ và hòn đảo thứ ~j~. Riêng với ~c_{i, i} = 0,\,\forall i = \overline{1..n}~.

Output

Nếu có thể thành công hoàn thành thử thách, in ra một dòng duy nhất một số nguyên là số lượng vàng lớn nhất có thể đạt được sau khi hoàn thành thử thách.

Nếu không thể hoàn thành thử thách, in ra "~-1~" (không bao gồm dấu ngoặc kép).

Scoring

Sample Input 1

3 10
0 1 1
1 0 1
1 1 0

Sample Output 1

7

Sample Input 2

3 0
0 1 1
1 0 1
1 1 0

Sample Output 2

-1

Có ~n~ cái kẹo trên bàn; người ta muốn cất kẹo vào trong một số túi sao cho mỗi túi chứa một số các viên kẹo nằm liên tiếp nhau trên bàn.

Đồng thời, mỗi túi có không quá ~m~ viên kẹo, và số kẹo trong hai túi liên tiếp hơn kém nhau không quá ~d~ viên.

Yêu cầu: Bạn hãy tính số cách chia kẹo vào túi thỏa mãn nhé. Hai cách chia được coi là khác nhau nếu số túi sử dụng là khác nhau, hoặc tồn tại một túi sao cho trong hai cách, số lượng kẹo tại túi đó khác nhau.

Input

Một dòng chứa ba số nguyên dương ~n, m, d~ (~n \le 10^{18}, d\le m \le 10~).

Output

In ra một số nguyên là số cách chia kẹo. Vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~10^9 + 7~.

Scoring

Sample Input 1

5 3 1

Sample Output 1

10

Notes

Ta có ~10~ cách chia:

• (1, 1, 1, 1, 1)

• (1, 1, 1, 2)

• (1, 1, 2, 1)

• (1, 2, 1, 1)

• (2, 1, 1, 1)

• (1, 2, 2)

• (2, 2, 1)

• (2, 1, 2)

• (2, 3)

• (3, 2)

Chú thích: Phần tử thứ ~i~ là số viên kẹo trong túi thứ ~i~ của cách chia.