Cho ba giá trị nguyên không âm ~n, s~ và ~m~.

Một viên ngọc có thể cấu tạo bởi ~n~ loại nguyên tố khác nhau. Với 1mg nguyên tố thứ ~i~ xuất hiện trong viên ngọc sẽ làm tăng giá trị viên ngọc thêm ~2^{i - 1}~ đơn vị.

Cấu tạo của hai viên ngọc là khác nhau nếu tồn tại một loại nguyên tố mà hàm lượng của của nguyên tố này trong viên ngọc ở hai cấu tạo là khác nhau.

Nhiệm vụ của bạn là đếm số lượng cấu tạo khác nhau của các viên ngọc có giá trị ~x~ sao cho ~0 \leq x \leq 2^n - 1~ và ~x \mod m = s~.

Giải thích về cấu tạo một viên ngọc: Giả sử viên ngọc có giá trị là ~x = 6~, các cấu tạo khác nhau có thể của viên ngọc là:

• 6mg nguyên tố thứ nhất: ~x = 6\times 2^0 = 6\times 1 = 6~.
• 4mg nguyên tố thứ nhất, 1mg nguyên tố thứ hai: ~x = 4\times 2^0 + 1\times 2^1 = 4\times 1 + 1\times 2 = 6~.
• 2mg nguyên tố thứ nhất, 2mg nguyên tố thứ hai: ~x = 2\times 2^0 + 2\times 2^1 = 2\times 1 + 2\times 2 = 6~.
• 2mg nguyên tố thứ nhất, 1mg nguyên tố thứ ba: ~x = 2\times 2^0 + 1\times 2^2 = 2\times 1 + 1\times 4 = 6~.
• 3mg nguyên tố thứ hai: ~x = 3\times 2^1 = 3\times 2 = 6~.
• 1mg nguyên tố thứ hai, 1mg nguyên tố thứ ba: ~x = 1\times 2^1 + 1\times 2^2 = 1\times 2 + 1\times 4 = 6~.

Dữ liệu - Nhập từ tệp văn bản PEARL.inp:

• Một dòng duy nhất chứa ba số nguyên ~n, s~ và ~m~ ~(1 \leq n \leq 100, 0 \leq s < m \leq 1000)~.

Kết quả - Ghi ra tệp văn bản PEARL.out:

• Một dòng duy nhất chứa kết quả bài toán. Do kết quả có thể rất lớn, hãy in ra dưới dạng modulo ~10^9 + 7~.

Chấm điểm

Ví dụ

Dữ liệu (PEARL.inp)

3 1 5

Kết quả (PEARL.out)

7

Giải thích

• Các giá trị ~x~ thoả mãn ~0 \leq x \leq 2^n - 1~ và ~x \mod m = s~ là ~1~ và ~6~. Với ~x = 1~ có ~1~ cấu tạo khác nhau, với ~x = 6~ có ~6~ cấu tạo khác nhau.

Dữ liệu (PEARL.inp)

7 0 100

Kết quả (PEARL.out)

9829

Giải thích

• Các giá trị ~x~ thoả mãn ~0 \leq x \leq 2^n - 1~ và ~x \mod m = s~ là ~0~ và ~100~. Với ~x = 0~ có ~1~ cấu tạo khác nhau, với ~x = 100~ có ~9828~ cấu tạo khác nhau.

Dữ liệu (PEARL.inp)

36 0 100

Kết quả (PEARL.out)

275724118