Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BINARY2 - SPBINARY2

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/binary2


Đề bài tương tự SPBINARY, nhưng giới hạn lớn hơn

Cho 2 số n và k ( 2<=k <= n <= 10^6)

Hãy đếm xem có bao nhiêu xâu nhị phân độ dài n mà không có quá k số 0 hoặc k số 1 nào liên tiếp nhau.

Input

Gồm 1 dòng duy nhất là 2 số n và k.

Output

Gồm 1 dòng duy nhất là số dãy nhị phân thoả mãn (module 10^9).

Example

Input:
3 2

Output:
6

Được gửi lên bởi:Minh^^
Ngày:2011-08-03
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED

hide comments
2012-10-10 12:40:06 Minh^^
1S nhé các bạn
2011-10-15 14:09:40 Doom Bringer
Time limit 0.1s á,PS xem lại dùm đi.

Last edit: 2011-10-15 14:11:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.