CF1895F Fancy Arrays

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 $ .

The 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 $ ).

For each test case, print a single integer — the number of fancy arrays of length $ n $ , taken modulo $ 10^9+7 $ .

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] $ .