Dãy chia hết

Một dãy chia hết là một dãy các số nguyên dương đôi một phân biệt \(d_1,d_2,\ldots,d_k\) sao cho với mọi \(i\):

• \(l \le d_i \le r\);
• nếu \(i>1\) thì \(d_i\) chia hết cho \(d_{i-1}\).

Bạn được cho hai số nguyên dương \(l,r\).

Yêu cầu:

• Xác định độ dài lớn nhất \(k\) có thể của một dãy chia hết.
• Đếm xem có bao nhiêu dãy chia hết có độ dài đúng bằng \(k\).

Vì số lượng dãy có thể rất lớn, chỉ cần in ra 9 chữ số cuối của số lượng dãy (tức là lấy modulo \(10^9\)).

Input

Hai dòng, dòng thứ nhất chứa \(l\), dòng thứ hai chứa \(r\) \((1 \le l \le r \le 10^{14})\).

Output

In ra hai số nguyên dương cách nhau bởi một dấu cách: \(k\) và (số lượng dãy độ dài \(k\)) modulo \(10^9\).

Sample Input 1

3
16

Sample Output 1

3 2