#2059. BITSTR

Ta gọi xâu nhị phân độ dài là dãy gồm kí hiệu, mỗi kí hiệu chỉ là hoặc . Như đã biết, có tất cả xâu như vậy. Trong bài toán này, ta chỉ quan tâm đến những xâu nhị phân độ dài chứa đoạn gồm số liên tiếp. Vì con số này là rất lớn khi và lớn, nên chỉ cần đưa ra phần dư trong phép chia của số này cho .

Cho trước hai số nguyên dương và , hãy tìm phần dư trong phép chia của số lượng xâu nhị phân độ dài chứa đoạn gồm số liên tiếp cho .

Dữ liệu vào:

• Một dòng duy nhất gồm hai số nguyên dương và .

Dữ liệu ra:

• In ra phần dư trong phép chia của số lượng xâu nhị phân thỏa mãn cho .

Ví dụ:

Dữ liệu vào:

3 2

Dữ liệu ra:

3

Dữ liệu vào:

5 1

Dữ liệu ra:

31

Dữ liệu vào:

7 10

Dữ liệu ra:

0

Giải thích:

• Ví dụ Có ba xâu: ;
• Ví dụ Có tất cả xâu nhị phân độ dài ngoại trừ ;
• Ví dụ Không có xâu thỏa mãn.