+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- برای هر عدد طبیعی $n$ مقدار $f(n)$ را برابر مجموع ارقام آن تعریف میکنیم. برای مثال $f(114514) = 1 + 1 + 4 + 5 + 1 + 4 = 16$ . برای هر $n$ و $k$ مقدار $g(n , k)$ را برابر با $f(f(...(f(n)...))$ تعریف می کنیم که در آن تابع $f$ دقیقا $k$ بار صدا زده شده است. عمو که بعد از دیدن این تعاریف به آن ها علاقه مند شده ، تصمیم می گیرد یه بازی هیجان انگیز به اسم جمعه انجام بدهد. او می خواهد $T$ دور جمعه بازی کند. در هر دور بازی سه عدد $N , m , k$ انتخاب می کند و باید تعداد $n$ های طبیعی را پیدا کند که $n \leq N$ و $g(n , k) = m$ باشد. عمو که فهمیده بود تنهایی از پس این بازی بر نمیاد از شما کمک می خواهد تا جواب هر دور از بازی را به پیمانه $10^9 + 7$ خروجی دهید. # ورودی در خط اول عدد $T$ ورودی داده می شود که نشانگر تعداد پرسش هاست. در هر یک از $T$ خط بعدی به شما سه عدد طبیعی $N,k,m$ به ترتیب ورودی داده می شوند. # خروجی به ازای هر پرسش جواب آن را به پیمانه $10^9 + 7$ خروجی دهید. # محدودیت ها $$ 1 \leq T \leq 5 $$ $$ 1 \leq N \leq 10^{1000}$$ $$ 1 \leq k , m \leq 10^9$$ ## ورودی نمونه ۱ ``` 2 114 1 5 514 2 10 ``` ## خروجی نمونه ۱ ``` 8 10 ``` در دور اول، مقدار $n$ می تواند برابر با 5 ، 14 ، 23 ، 32 ، 41 ، 50 ، 104 و 113 باشد تا $g(n,1) = 5$ برقرار باشد.

حل سؤال در بانک سؤالات