310830: CF1895F. Fancy Arrays
Memory Limit:512 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
F. Fancy Arraystime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output
Let's call an array $a$ of $n$ non-negative integers fancy if the following conditions hold:
- at least one from the numbers $x$, $x + 1$, ..., $x+k-1$ appears in the array;
- consecutive elements of the array differ by at most $k$ (i.e. $|a_i-a_{i-1}| \le k$ for each $i \in [2, n]$).
You are given $n$, $x$ and $k$. Your task is to calculate the number of fancy arrays of length $n$. Since the answer can be large, print it modulo $10^9+7$.
InputThe first line contains a single integer $t$ ($1 \le t \le 50$) — the number of test cases.
The only line of each test case contains three integers $n$, $x$ and $k$ ($1 \le n, k \le 10^9$; $0 \le x \le 40$).
OutputFor each test case, print a single integer — the number of fancy arrays of length $n$, taken modulo $10^9+7$.
ExampleInput4 3 0 1 1 4 25 4 7 2 1000000000 40 1000000000Output
9 25 582 514035484Note
In the first test case of the example, the following arrays are fancy:
- $[0, 0, 0]$;
- $[0, 0, 1]$;
- $[0, 1, 0]$;
- $[0, 1, 1]$;
- $[0, 1, 2]$;
- $[1, 0, 0]$;
- $[1, 0, 1]$;
- $[1, 1, 0]$;
- $[2, 1, 0]$.
Output
题目大意:
定义一个非负整数数组a为“花哨”(fancy),如果满足以下条件:
- 数组中至少包含一个数x, x+1, ..., x+k-1;
- 数组中相邻元素之差最多为k(即对于每个i ∈ [2, n],有|a_i - a_(i-1)| ≤ k)。
给定n, x和k,任务是计算长度为n的“花哨”数组的数量。由于答案可能很大,结果需要模上10^9+7。
输入数据格式:
第一行包含一个整数t(1 ≤ t ≤ 50)——测试用例的数量。
每个测试用例包含一行,有三个整数n, x和k(1 ≤ n, k ≤ 10^9; 0 ≤ x ≤ 40)。
输出数据格式:
对于每个测试用例,输出一个整数——长度为n的“花哨”数组的数量,模上10^9+7。题目大意: 定义一个非负整数数组a为“花哨”(fancy),如果满足以下条件: - 数组中至少包含一个数x, x+1, ..., x+k-1; - 数组中相邻元素之差最多为k(即对于每个i ∈ [2, n],有|a_i - a_(i-1)| ≤ k)。 给定n, x和k,任务是计算长度为n的“花哨”数组的数量。由于答案可能很大,结果需要模上10^9+7。 输入数据格式: 第一行包含一个整数t(1 ≤ t ≤ 50)——测试用例的数量。 每个测试用例包含一行,有三个整数n, x和k(1 ≤ n, k ≤ 10^9; 0 ≤ x ≤ 40)。 输出数据格式: 对于每个测试用例,输出一个整数——长度为n的“花哨”数组的数量,模上10^9+7。
定义一个非负整数数组a为“花哨”(fancy),如果满足以下条件:
- 数组中至少包含一个数x, x+1, ..., x+k-1;
- 数组中相邻元素之差最多为k(即对于每个i ∈ [2, n],有|a_i - a_(i-1)| ≤ k)。
给定n, x和k,任务是计算长度为n的“花哨”数组的数量。由于答案可能很大,结果需要模上10^9+7。
输入数据格式:
第一行包含一个整数t(1 ≤ t ≤ 50)——测试用例的数量。
每个测试用例包含一行,有三个整数n, x和k(1 ≤ n, k ≤ 10^9; 0 ≤ x ≤ 40)。
输出数据格式:
对于每个测试用例,输出一个整数——长度为n的“花哨”数组的数量,模上10^9+7。题目大意: 定义一个非负整数数组a为“花哨”(fancy),如果满足以下条件: - 数组中至少包含一个数x, x+1, ..., x+k-1; - 数组中相邻元素之差最多为k(即对于每个i ∈ [2, n],有|a_i - a_(i-1)| ≤ k)。 给定n, x和k,任务是计算长度为n的“花哨”数组的数量。由于答案可能很大,结果需要模上10^9+7。 输入数据格式: 第一行包含一个整数t(1 ≤ t ≤ 50)——测试用例的数量。 每个测试用例包含一行,有三个整数n, x和k(1 ≤ n, k ≤ 10^9; 0 ≤ x ≤ 40)。 输出数据格式: 对于每个测试用例,输出一个整数——长度为n的“花哨”数组的数量,模上10^9+7。