Một bạn tân sinh viên của IUH có tên ~s~ (là chuỗi ký tự in hoa viết liền không dấu) và số điện thoại là chuỗi ~t~ gồm các ký tự từ ~0~ đến ~9~. Bạn muốn lập mật khẩu theo một trong ba lựa chọn sau:

1. Mật khẩu là hoán vị các chữ cái trong tên.
2. Mật khẩu là hoán vị các chữ số trong số điện thoại.
3. Mật khẩu có độ dài ~m~, sử dụng các ký tự có trong ~s, t~ sao cho các chữ cái, chữ số được xếp xen kẽ nhau (các ký tự không nhất thiết phân biệt).

Hãy giúp bạn này tính số mật khẩu có thể có cho mỗi lựa chọn trên.

Input

Một dòng duy nhất gồm chuỗi s, chuỗi ~t~ và số ~m~ cho biết rằng ~1 \le |s| \le 19, |t| = 10~ và ~1 \le m \le 10^3.~

Output

Một dòng duy nhất gồm ba kết quả (mỗi số cách nhau bởi một khoảng trắng), là số lượng mật khẩu có thể có, tính theo modulo ~10^9 + 7.~

Sample Input

MEOSUA 0909123456 2

Sample Output

720 907200 96