DIVSEQ - DIVSEQ

You're given two numbers - N and K  (0 < N, K <= 1000). You have to count the number of sequences of positive integers with length N where every element must be not greater than K and for every two consecutive elements with indices i and i + 1 one of the conditions bellow must be true:

  1. a[i] is divisible by a[i + 1]
  2. a[i + 1] is divisible by a[i]

Input

On the only line you will be given the values of N and K.

Output

Print the number of the sequences described above modulо 1000000009.

Example

Input:
2 4

Output:
12

Added by:ivokaragyozov
Date:2016-03-03
Time limit:0.200s-0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:http://www.math.bas.bg/infos/files/2013-05-02-C1.pdf

hide comments
2024-07-13 06:33:21
CHECK: scanf,printf - got RE, cin,cout - got AC
2021-09-28 08:24:30
Get Accepted in 1 go! : )
Nice dp problem.

Last edit: 2021-09-28 08:25:24
2017-04-04 12:27:34 SUBHAM SANGHAI
Note, Mod is 10^9+9 not 10^9+7
2017-04-04 08:09:45
I am getting a runtime error on test case 15. I cannot figure out where did i go out of bounds. Can someone help??


Last edit: 2017-04-04 08:12:04
2016-03-09 17:18:44 darryl
Then what about the condition about consecutive integers a[i] and a[i+1] that must be true? When N=1, no such consecutive integers exist so this condition cannot be true.
2016-03-09 10:49:10 ivo2001
Because when N = 1 every integer smaller or equal to K can be in the sequance so the answer is K
2016-03-09 05:45:53 darryl
why when N=1, the answer is not 0?

Last edit: 2016-03-09 05:46:39
2016-03-08 06:24:07
Here's a reword of the problem:

You are given two integers, N and K. Both N and K are in the range of 1 to 1000 inclusive.

Find the amount of integer sequences of length N where each integer in the sequence is both:
1) Less than or equal to K
2) Is divisible or a multiple of its adjacent neighbors.

Hopefully, that makes it more clear for others who were confused like me.
2016-03-04 10:09:28 ivo2001
Explanation of the example:
The sequences must be of length 2 and they can only contain the numbers to 4, so the possible sequences are:
[1, 1]; [1, 2]; [1, 3]; [1, 4]; [2, 1]; [2, 2]; [2, 4]; [3, 1]; [3, 3]; [4, 1]; [4, 2]; [4, 4].

But you can see that sequence [2, 3] is not correct because 2 is not divisible by 3 and 3 is not divisible by 2
2016-03-04 10:00:25 ivo2001
You must count the number of sequences A of length N where 1<=A[i]<=K and for every two consecutive elements - A[i] and A[i + 1] must be true A[i] is divisible by A[i + 1] OR A[i + 1] is divisible by A[i].

Last edit: 2016-03-04 10:00:41
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.