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
2021-05-27 17:59:12
Tham khảo: https://vnspoj.github.io/problems/BINARY2
2019-07-21 15:06:55
1 đấm AC :))
2018-11-05 15:01:12
mat 1 dam vi quen xu li so am khi mod :'(
2018-10-19 10:50:08
https://ideone.com/OCBwSJ
2017-07-20 18:49:06
mất 1 đấm vì mod nhầm cho 10^9+7
2017-07-07 17:12:53
duyệt trâu 1 đấm AC
2016-09-27 03:11:29
Code AC
http://shink.in/oJGX6
2016-09-25 14:53:07 Phạm Huỳnh Nhật
O(n).....http://ideone.com/gBgnIe...chỉ để tham khảo
2016-08-05 15:39:48
vl bài 2 mà dễ hơn bài 1 nữa :v
2015-10-27 19:47:24
Blog Thuật toán SPOJ hy vọng giúp được cho mọi người : http://www.oni.vn/uR57W
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.