#include #include #include #include #include using namespace std; const long M_MAX = 1e10; const int UNIT = 111111; const int MOD = 1e9 + 9; int main() { int limit = M_MAX / UNIT; vector dp(limit + 1, 1); for (int coin = 1; coin <= 9; coin++) { for (int i = coin; i <= limit; i++) { dp[i] = (dp[i - coin] + dp[i]) % MOD; } } int t, m; cin >> m; vector ans(m, 0); for (int i = 0; i < m; i++) { cin >> t; ans[i] = dp[t / UNIT]; } for (int i = 0; i < m; i++) { cout << ans[i] << endl; } return 0; }