Có ~n~ thành phố và ~m~ chuyến bay kết nối giữa chúng. Bạn muốn đi từ Syrjälä đến Lehmälä để bạn đến thăm mỗi thành phố đúng một lần. Có bao nhiêu tuyến đường khả thi?

Input

• Dòng đầu tiên là hai số nguyên ~n~ và ~m~: số thành phố và chuyến bay. Các thành phố được đánh số ~1,2,\ldots, n~. Thành phố ~1~ là Syrjälä, và thành phố ~n~ là Lehmälä.
• Sau đó, có ~m~ dòng mô tả các chuyến bay. Mỗi dòng gồm hai số nguyên ~a~ và ~b~: có một chuyến bay từ thành phố ~a~ đến thành phố ~b~. Tất cả các chuyến bay đều là chuyến bay một chiều.

Output

• In ra một số nguyên: số tuyến đường theo modulo ~10^9 + 7~.

Constraints

• ~2 \le n \le 20~
• ~1 \le m \le n^2~
• ~1 \le a, b \le n~

Example

Sample Input

4 6
1 2
1 3
2 3
3 2
2 4
3 4

Sample Output

2

Cho dãy ~a~ gồm ~n~ phần tử nguyên dương. Với mỗi phần tử ~i~, hãy in ra số phần tử ~j~ thỏa mãn ~a_i \& a_j = a_j~, với ~\&~ là phép AND. Nói cách khác, với mỗi phần tử ~i~, hãy in ra số phần tử ~j~ thỏa mãn ~a_j~ là ~submask~ của ~a_i~.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả số phần tử trong dãy.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ miêu tả số phần tử ~j~ thỏa mãn ~a_j~ là ~submask~ của ~a_i~.

Constraints

• ~1 \le n \le 2*10^5~.
• ~0 < a_i < 2^{16}~.

Subtasks

• Subtask ~1~: ~n \le 1000~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Sample Input 1:

5
2 3 4 5 2

Sample Output 1:

2
3
1
2
2

Có ~N~ con thỏ được đánh số ~1,2,3,...,N~

Với mỗi ~i,j(1\le i,j\le N)~, độ "tâm đầu ý hợp" của con thỏ ~i~ và ~j~ được kí hiệu bởi một số nguyên ~a_{i,j}~. Ở đây ~a_{i,i}=0~ với mọi ~i(1\le i\le N),a_{j,i}=a_{i,j}~ với mọi ~i,j(1\le i,j\le N)~.

~Kaninho~ chia ~N~ con thỏ này thành nhiều nhóm. Ở đây, mỗi con thỏ thuộc về chính xác ~1~ nhóm. Sau khi chia xong, với mỗi cặp ~i,j(1\le i<j\le N)~. ~Kaninho~ sẽ kiếm được ~a_{i,j}~ điểm nếu con thỏ ~i~ và ~j~ cùng thuộc về một nhóm.</p>

Tìm số điểm tối đa mà ~Kaninho~ có thể thu được.

Input

• Dòng thứ nhất chứa số nguyên ~N~.
• ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên ~a_{i,1},a_{i,2},...,a_{i,N}~ thể hiện độ "tâm đầu ý hợp" của những chú thỏ với nhau.

Output

• In ra kết quả cần tìm.

Constraints

• ~1\le i\le N,|a_{i,j}|\le 10^9~
• ~1\le N\le 16~

Example

Sample Input

3
0 10 20
10 0 -100
20 -100 0 

Sample Output

20

Note

Những con thỏ chia thành hai nhóm ~(1,3),(2)~. Khi đó số điểm tối đa mà ~Kaninho~ nhận được là ~20~.

Messi đang muốn đi tập Gym để chụp hình đăng Instagram. Phòng Gym của anh có ~n~ quả tạ được đánh số từ ~1~ tới ~n~. Quả tạ thứ ~i~ có trọng lượng ~w_i~.

Vì là GOAT, Messi có thể nâng nhiều tạ một lúc, tuy nhiên, các tạ mà anh ấy chọn sẽ phải tuân thủ điều kiện sau:

• Đối với mọi chữ số từ ~0~ tới ~9~, số lần chữ số đó xuất hiện trong các tạ được chọn không vượt quá ~2~.

Ví dụ, Messi có thể nâng các tạ ~[10,8,1]~ nhưng không thể nâng tạ ~[700,70]~ vì số ~0~ lặp lại ~3~ lần.

Vì muốn có một cơ bắp nhìn quá là ưng, hãy in ra trọng lượng tối đa của các tạ mà Messi có thể mang.

Input

• Dòng đầu tiên gồm số hai nguyên dương ~n~ ~(1\le n \le 100)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~w~ ~(1 \le w_i \le 10^9)~.

Output:

• In ra kết quả của bài toán.

Sample Input 1

4
99 9 58 72

Sample Output 1

229

Sample Input 2

1
777

Sample Output 2

0