#include #include #include using namespace std; typedef long long ll; ll MOD = 1000 * 1000 * 1000 + 9; const auto PRICE1 = 111111; int main() { int T; cin >> T; while (T--) { ll M; cin >> M; vector dp(M / PRICE1 + 1, 0); dp[0] = 1; for (auto price = 1; price <= 9; price++) { for (auto use = 0; use < dp.size(); use++) { if (use - price < 0) continue; dp[use] += dp[use - price]; dp[use] %= MOD; } } ll ans = 0; for (auto ways : dp) { ans += ways; ans %= MOD; } cout << ans << endl; } return 0; }