SP26527 DIVSEQ - DIVSEQ
题目描述
给定两个整数 $N$ 和 $K$（$0 < N, K \leq 1000$）。请计算所有符合以下条件的正整数序列的数量：
- 序列长度为 $N$。
- 序列中的每个元素都不大于 $K$。
- 对于相邻的两个元素 $a[i]$ 和 $a[i + 1]$，必须满足以下条件之一：
1. $a[i]$ 能整除 $a[i + 1]$。
2. $a[i + 1]$ 能整除 $a[i]$。
输入格式
输入包含一行，两个整数 $N$ 和 $K$。
输出格式
输出符合条件的序列数量对 $1000000009$ 进行取模后的结果。
### 示例
```
输入：
2 4
输出：
12
```
## 数据范围
- $0 < N, K \leq 1000$
**本翻译由 AI 自动生成**