DIVSEQ  DIVSEQ
You're given two numbers  N and K (0 < N, K <= 1000). You have to count the number of sequances of positive integers with length N where every element must be not greater than K and for every two consecutive elements with indeces i and i + 1 one of the conditions bellow must be true:
 a[i] is divisible by a[i + 1]
 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
hide comments
SUBHAM SANGHAI:
20170404 12:27:34
Note, Mod is 10^9+9 not 10^9+7 

rajat_jain21:
20170404 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??


darryl:
20160309 17:18:44
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. 

ivo2001:
20160309 10:49:10
Because when N = 1 every integer smaller or equal to K can be in the sequance so the answer is K


darryl:
20160309 05:45:53
why when N=1, the answer is not 0? Last edit: 20160309 05:46:39 

quocanhvu:
20160308 06:24:07
Here's a reword of the problem:


ivo2001:
20160304 10:09:28
Explanation of the example:


ivo2001:
20160304 10:00:25
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: 20160304 10:00:41 

gurugs:
20160303 20:21:29
i am getting all WAs 

gurugs:
20160303 20:20:09
someone explain the problem please...especially the meaning "every element not greater than K" and the two conditions ...explain the test case also...thanks in advance 
Added by:  ivokaragyozov 
Date:  20160303 
Time limit:  0.200s0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  http://www.math.bas.bg/infos/files/20130502C1.pdf 