Trong tiết học môn Nhập môn Công nghệ Thông tin, bạn ~H~ đã được học về các phép toán trên bit (bitwise operations). Rất hứng thú với các phép toán này, bạn ~H~ đã định nghĩa một cặp số đáng yêu như sau:

Một cặp số đáng yêu là một cặp 2 số ~a~ và ~b~ khác nhau sao cho:

$$(a \oplus b) \equiv (a \land b) \mod k$$

Với:

• ~\oplus~ là phép toán XOR.

• ~\land~ là phép toán AND.

Bạn ~H~ đi khoe với mọi người về cặp số đáng yêu của mình và sau đó đố ~U~ xem là có bao nhiêu cặp số đáng yêu ~(a, b)~ sao cho ~L \le a < b \le R~. Bạn hãy giúp ~U~ tìm ra đáp án nhé!

Input

Gồm một dòng duy nhất chứa 3 số nguyên dương lần lượt là ~l~, ~r~ và ~k~ (~1 \le l \le r \le 10^{18};\ k \le 10^4~).

Output

Gồm một dòng duy nhất chứa 1 số nguyên không âm duy nhất là số lượng cặp số đáng yêu cần tìm đem chia dư với ~10^9+7~.

Scoring

• Subtask ~1~ (~30~ điểm): ~r-l \le 1000~.

• Subtask ~2~ (~30~ điểm): ~l=1~.

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

Sample Input 1

1 10 3

Sample Output 1

15

Notes

Trong test ví dụ thứ nhất, dưới đây là 15 cặp số đáng yêu thỏa mãn: