SPOJ.com - Problem DIVSEQ

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:

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

Submit solution!

hide comments

< Previous 1 2 Next >

	vl4deee11: 2024-07-13 06:33:21 CHECK: scanf,printf - got RE, cin,cout - got AC
	cjn2007: 2021-09-28 08:24:30 Get Accepted in 1 go! : ) Nice dp problem. Last edit: 2021-09-28 08:25:24
	SUBHAM SANGHAI: 2017-04-04 12:27:34 Note, Mod is 10^9+9 not 10^9+7
	rajat_jain21: 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
	darryl: 2016-03-09 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: 2016-03-09 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: 2016-03-09 05:45:53 why when N=1, the answer is not 0? Last edit: 2016-03-09 05:46:39
	quocanhvu: 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.
	ivo2001: 2016-03-04 10:09:28 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
	ivo2001: 2016-03-04 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: 2016-03-04 10:00:41

Submit solution!

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