A higher resolution is required to access the IDE
- 28
Learning Opportunities
This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.
Statement
Goal
Pascal's Triangle is a famous mathematical structure, in which the binomial coefficients are arranged in a triangular fashion. It is commonly generated recursively by defining the 0'th row/column as 1, padding each subsequent row with two 1's, and applying the recurrence:C(n, k) = C(n-1, k-1) + C(n-1, k)
...where n and k represent the indices of the the triangle's rows and columns respectively. This produces the following collection of integers for the first few rows:
[0]|1
[1]|1 1
[2]|1 2 1
[3]|1 3 3 1
[4]|1 4 6 4 1
[5]|1 5 10 10 5 1
[6]|1 6 15 20 15 6 1
etc...
In addition to its many practical applications in mathematics, Pascal's triangle also has many unusual and fascinating properties. One of its most intriguing characteristics pertains to divisibility, and can be demonstrated by shading all cells in the triangle that are not divisible by a given number (henceforth referred to as P). This expands into an infinite fractal pattern that closely resembles the well-known Sierpinski triangle. For example, here are the first 12 rows of the fractal that is formed when P = 3:
[01]|# (1)
[02]|## (2)
[03]|### (3)
[04]|#__# (2)
[05]|##_## (4)
[06]|###### (6)
[07]|#__#__# (3)
[08]|##_##_## (6)
[09]|######### (9)
[10]|#________# (2)
[11]|##_______## (4)
[12]|###______### (6)
etc...
Given three integers P, R, and C, your task is to count the number of shaded cells in the first R rows and C columns of the resulting fractal. You can assume that the triangle's values are all left-aligned and displayed in the form of a two-dimensional matrix (as in the example above). As C(n, k) is undefined for k > n, disregard any cells where the column index is greater than the row. As the resulting numbers can be quite massive, print your answer modulo
============================================================================
[Example]:
P = 3
R = 12
C = 6
[01]|# (1)
[02]|## (2)
[03]|### (3)
[04]|#__# (2)
[05]|##_## (4)
[06]|###### (6)
[07]|#__#__. (2)
[08]|##_##_.. (4)
[09]|######... (6)
[10]|#_____.... (1)
[11]|##____..... (2)
[12]|###___...... (3)
('#' -- shaded)
('_' -- unshaded)
('.' -- out of bounds)
Result = (1 + 2 + 3 + 2 + 4 + 6 + 2 + 4 + 6 + 1 + 2 + 3) % 1000000007 = 36
Input
Line 1: A single integer, T, denoting the number of test cases.
Next T lines: Three space-separated integers, P, R, and C, for a test case.
Next T lines: Three space-separated integers, P, R, and C, for a test case.
Output
T lines: A single integer representing the number of shaded cells in the first R rows and C columns of the fractal that is formed after shading all cells that are non-divisible by P for a test case. Output your results modulo 1000000007 .
Constraints
1 ≤ T ≤ 100
1 ≤ R, C ≤ 10^19
3 ≤ P ≤ 17
P is prime.
1 ≤ R, C ≤ 10^19
3 ≤ P ≤ 17
P is prime.
Example
Input
11 3 12 6 5 47 47 5 114 114 13 13 13 5 3 3 7 20 20 13 61 25 13 12 4 11 63 27 5 68 68 17 43 8
Output
36 555 2625 91 6 147 724 42 831 1017 260
A higher resolution is required to access the IDE