Sau khi ra khỏi phòng thi TST, sangph2612 thở dài vì đã "tạch", định móc điện thoại từ trong cặp ra để tâm sự với người yêu thì phát hiện điện thoại đã không cánh mà bay. Một kí ức bỗng xẹt ngang qua đầu Sang, trước khi vào phòng thi, anh ấy đã đưa chiếc điện thoại "yêu dấu" của mình cho một người bạn mà anh ấy chẳng nhớ tên cũng chẳng nhớ mặt. Quá buồn vì ~2~ cú sốc trong cùng một ngày, lại không thể nhắn tin thường xuyên với người yêu mà cũng không chơi game được; vì vậy, bằng đầu óc thông minh của mình, Sang đã tự sáng tạo ra một trò chơi mà chỉ mình anh ấy thấy thú vị. Sang viết lên giấy một dãy số bất kì có ~N~ phần tử có giá trị trong đoạn ~[1,32]~, Sang tự thử thách mình bằng cách thêm vào dãy số đã viết đúng ~K~ phần tử cũng có giá trị trong đoạn ~[1,max(a_i)]~, với ~max(a_i)~ là phần tử lớn nhất trong dãy số ban đầu, sao cho dãy số lúc sau là một dãy số đẹp. Đối với một người yêu số học như Sang, dãy số đẹp là dãy số mà ước chung lớn nhất của ~i~ và ~j~ bắt buộc phải có mặt nếu ~i~ và ~j~ có mặt trong dãy số đã viết. Nhưng không dừng lại ở đó, Sang lại thách thức những người bạn của mình phải đếm được số dãy đẹp có thể có, biết rằng thứ tự các số trên dãy số đã viết là không quan trọng., nghĩa là ~[1,2,3]~ và ~[3,1,2]~ là như nhau.

Yêu cầu: Một trong những người bạn của Sang rất ngốc nên đã nhờ đến sự giúp đỡ của bạn. Hãy giúp người bạn ấy đếm số dãy đẹp có thể có nhé.

Dữ liệu vào

• Dòng đầu tiên chứa ~2~ số nguyên ~N~, ~K~ ~(1 \le N, K \le 32)~ lần lượt là số lượng số ban đầu được viết trên giấy và số lượng số cần phải thêm vào.
• Dòng thứ hai gồm ~N~ số nguyên ~a_i~ ~(1 \le a_i \le 32, 1 \le i \le N)~ là các số ban đầu được viết trên giấy. Biết rằng có ít nhất một số ~1~ trong dãy số ban đầu.

Dữ liệu ra

Một số nguyên duy nhất là số lượng dãy đẹp có thể có. Kết quả có thể rất lớn nên hãy in ra số dư của kết quả khi chia cho ~10^9 + 7~.

Giới hạn

• Subtask 1 (40% số điểm): ~N,K,max(a_i) \le 15~
• Subtask 2 (60% số điểm): ~N,K,max(a_i) \le 32~

Ví dụ 1

Input

3 1 
1 6 9

Output

1

Ví dụ 2

Input

3 1 
3 1 2

Output

3

Giải thích

• Ở ví dụ ~1~, ta có ~GCD(6,9)~ là ~3~ và ~3~ chưa xuất hiện trong dãy số nên để tạo thành dãy đẹp và chỉ thêm đúng ~1~ số duy nhất, nên ta chỉ có thể thêm ~3~ vào dãy. Vậy nên đáp án là ~1~.
• Ở ví dụ ~2~, ta có ~GCD(1,3) = 1~, ~GCD(1,2) = 1~, ~GCD(3,2) = 1~ đều xuất hiện trong dãy nên ta có thể thêm bất kì số nào trong ~3~ số ~1~, ~2~, ~3~. Vậy nên, đáp án là ~3~.