using System; internal class Program { public static void Main(string[] args) { var t = int.Parse(Console.ReadLine()); Tuple[] values = new Tuple[t]; long[] results = new long[t]; for (int i = 0; i < t; i++) { values[i] = new Tuple(i, long.Parse(Console.ReadLine()) / 111111); } Array.Sort(values, (tuple, tuple1) => tuple.Item2.CompareTo(tuple1.Item2)); long maxValue = values[values.Length - 1].Item2; long[] dp = new long[maxValue + 1]; for (long i = 0; i < dp.Length; i++) { dp[i] = 1; } for (int number = 1; number <= 9; number++) { for (long j = number; j < dp.Length; j++) { const long mod = 1000000009; dp[j] = (dp[j] + dp[j - number]) % mod; } } for (int i = 0; i < t; i++) { if (values[i].Item2 == 0) { results[values[i].Item1] = 1; } else { results[values[i].Item1] = dp[values[i].Item2]; } } for (int i = 0; i < t; i++) { Console.WriteLine(results[i]); } } }