# Xây dựng hàng rào
Trung có cần xây dựng một hàng ràng có độ dài $m$.

Hiện tại Trung đang có $n$ loại thanh gỗ khác nhau, thanh gỗ loại $i$ có độ cao $i$ và có số lượng vô hạn thanh gỗ mỗi loại.

Gọi $h_i$ là độ cao của thanh gỗ ở vị trí $i$, Trung cần xây dựng một hàng rào đẹp thỏa mãn các tính chất sau:

* $h_1$ có thể nhận một giá trị bất kì.
* Nếu $2 \cdot h_i > n$, $h_{i+1}$ có thể nhận giá trị bất kì.
* Nếu $2 \cdot h_i \leq n$, $h_{i+1} \geq h_i$.
* $2 \cdot h_m > n$.

Giúp Trung tính số lượng hàng rào đẹp có thể xây dựng, chia lấy dư cho 1e9+7.

Subtask $1$ ($20$ điểm): $n, m \leq 300$.

Subtask $2$ ($30$ điểm): $n, m \leq 3000$.

Subtask $3$ ($50$ điểm): không có ràng buộc gì thêm.

# Lời giải

Dựa vào điều kiện $2 \cdot h_i > n$, $h_{i+1}$ có thể nhận giá trị bất kì, ta chia dãy độ dài $m$ ra thành các phần, mỗi phần bắt đầu là một giá trị bất kì và kết thúc khi thỏa mãn điều kiện (2).

Dựa vào điều kiện (3), ta nhận thấy mỗi phần có độ dài tối đa là log2(n), từ đó ta có công thức:

$f[i][len]$ là số phần bắt đầu bằng thanh gỗ độ dài $i$, và phần này có độ dài $len$.
$f[i][len]$ = $\sum\limits_{j = i*2}^{n}$ $f[j][len-1]$.
Ta có thể tính nhanh $f[i][len]$ trong O(1) bằng tổng tiền tố.

Gọi $cnt[len]$ là số phần có độ dài $len$, ta có $cnt[len]$ = $\sum\limits_{i=1}^{n}$ $f[i][len]$.

Gọi $dp[i]$ số hàng rào đẹp độ dài $i$, $cnt[i]$ = $\sum\limits_{j=1}^{min(log2(n), i)}$ $cnt[j] \cdot dp[i-j]$.