Dãy số tổng - tích

Hôm nay là ngày Nam phải học Toán, một trong những môn mà cậu ấy kém nhất. Thầy giáo của Nam yêu cầu phải tìm ra một dãy số gồm $k$ phần tử nguyên dương $a_1,a_2,\dots ,a_k$ thỏa mãn đồng thời hai điều kiện sau với mọi cặp phần tử kề nhau $a_i,a_{i+1}$ ($1\le i<k$):

• Tích hai số cạnh nhau không vượt quá $P$, tức là $a_i·a_{i+1}\le P$;
• Tổng hai số cạnh nhau không vượt quá $S$, tức là $a_i+a_{i+1}\le S$.

Nam rất mệt mỏi khi phải đếm hết tất cả các dãy số thỏa mãn vì số lượng của chúng quá lớn, nên cậu ấy phải nhờ các bạn lập trình.

Yêu cầu: Hãy giúp Nam đếm số lượng dãy số độ dài $k$ thỏa mãn các điều kiện trên. Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ${10}^9+7$.

Dữ liệu vào

Một dòng duy nhất chứa ba số nguyên dương $P,S,k$.

Dữ liệu ra

In ra một số nguyên duy nhất là phần dư của số lượng dãy số thỏa mãn khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le P,S\le {10}^9$.
• $2\le k\le 50$ (với $k=1$ dãy không có cặp kề nhau nào nên có vô số dãy, vì vậy $k\ge 2$).

Subtasks

• Subtask 1 ($20\%$ số test): $P,S\le 20$, $k\le 5$.
• Subtask 2 ($30\%$ số test): $P,S\le {10}^3$, $k\le 10$.
• Subtask 3 ($30\%$ số test): $P\le {10}^5$, $S\le {10}^9$, $k\le 50$.
• Subtask 4 ($20\%$ số test): không có ràng buộc gì thêm.

Ví dụ