• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۱۰۲۴ مگابایت

برای هر عدد طبیعی $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$ برقرار باشد.