{"problem":{"name":"[COCI 2023/2024 #1] Kocke","description":{"content":"在 Donald 的十三岁生日上，他的父亲给了他一套乐高积木。在这套积木中，有 $n$ 个大小相同的积木，且第 $i$ 个积木的颜色为 $i$ 。他想要用这些积木搭一面墙。 Donald 将在排成一排的乐高积木的底座上建造他的墙，底座上有 $k$ 个可以放积木的地方。他按以下方式放置积木： - 首先，他将颜色为 $1$ 的积木放在底座的任意一个位置上。 - 对于每个颜色从 $2$ 到 $n$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9906"},"statements":[{"statement_type":"Markdown","content":"在 Donald 的十三岁生日上，他的父亲给了他一套乐高积木。在这套积木中，有 $n$ 个大小相同的积木，且第 $i$ 个积木的颜色为 $i$ 。他想要用这些积木搭一面墙。\n\nDonald 将在排成一排的乐高积木的底座上建造他的墙，底座上有 $k$ 个可以放积木的地方。他按以下方式放置积木：\n\n- 首先，他将颜色为 $1$ 的积木放在底座的任意一个位置上。\n- 对于每个颜色从 $2$ 到 $n$ 的积木，他都会选择和前一个积木相邻的位置，在对应位置的顶端放上这个积木。\n\n他用一个长度为 $k$ 序列表示这面墙：对于第 $i$ 位，如果个位置没有积木，则是 $0$，否则是这个位置最顶端积木的颜色。\n\n问一共有多少种不同的序列，对 $10^9+7$ 取模。\n\n## Input\n\n一行两个整数 $n,k$ 表示积木数量和位置数量。\n\n## Output\n\n一个整数表示问题答案对 $10^9+7$ 取模的结果。\n\n[samples]\n\n## Note\n\n### 【样例解释#1】\n\n可能的序列有：$(0, 3, 4), (2, 3, 4), (0, 4, 3), (1, 4, 3), (4, 3, 0), (4, 3, 2), (3, 4, 0), (3, 4, 1)$。\n\n### 【样例解释#2】\n\n其中一种可能的序列是 $(0,3,2,0,0)$，它的操作步骤是：\n\n- 在第 $2$ 个位置顶端摆放编号为 $1$ 的积木。\n- 在第 $3$ 个位置顶端摆放编号为 $2$ 的积木。\n- 在第 $2$ 个位置顶端摆放编号为 $3$ 的积木。\n- 在第 $3$ 个位置顶端摆放编号为 $4$ 的积木。\n- 在第 $2$ 个位置顶端摆放编号为 $5$ 的积木。\n\n### 【数据范围】\n\n对于 $100\\%$ 的数据，$2\\leq n,k\\leq 5000$。\n\n**本题采用捆绑测试。**\n\n| 子任务 | 特殊性质 | 分值 |\n| :----------: | :----------: | :----------: |\n| $1$ | $n,k\\leq 18$ | $20$ |\n| $2$ | $n,k\\leq 50$ | $30$ |\n| $3$ | $n,k\\leq 500$ | $30$ |\n| $4$ | 无特殊性质 | $30$ |\n\n### 【说明】\n\n本题分值按 COCI 原题设置，满分 $110$。\n\n题目译自 [COCI2023-2024](https://hsin.hr/coci/archive/2023_2024/) [CONTEST #1](https://hsin.hr/coci/archive/2023_2024/contest1_tasks.pdf) _**T4 Kocke**_。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9906","tags":["2023","O2优化","COCI（克罗地亚）"],"sample_group":[["4 3","8"],["3 5","14"],["100 200","410783331"]],"created_at":"2026-03-03 11:09:25"}}