1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #define MOD 1000000009
  6. using namespace std;
  8. const int MAXN = 1000100;
  9. int n, m, a, b, q;
  10. long long x;
  11. struct node
  12. {
  13. long long val, lazy;
  14. };
  15. node tree[4*MAXN];
  17. void build(int begin, int end, int index)
  18. {
  19. if(begin == end)
  20. {
  21. tree[index].val = 1;
  22. tree[index].lazy = 1;
  23. return;
  24. }
  25. int mid = (begin+end)>>1;
  26. build(begin, mid, index*2);
  27. build(mid+1, end, index*2+1);
  28. tree[index].val = tree[index*2].val+tree[index*2+1].val;
  29. tree[index].lazy = 1;
  30. }
  32. long long upd_value;
  34. void update(int begin, int end, int i, int j, int index, long long xx)
  35. {
  36. if(begin >= i and end <= j)
  37. {
  38. //printf("%d %d\n", tree[index].val, tree[index].lazy);
  39. tree[index].lazy = (tree[index].lazy*xx)%MOD;
  40. tree[index].val = (tree[index].val*tree[index].lazy)%MOD;
  41. //printf("%d %d\n", tree[index].val, tree[index].lazy);
  42. return;
  43. }
  45. int mid = (begin+end)>>1;
  46. if(tree[index].lazy > 1)
  47. {
  48. tree[index*2].val = (tree[index*2].val*tree[index].lazy)%MOD;
  49. tree[index*2+1].val = (tree[index*2+1].val*tree[index].lazy)%MOD;
  50. tree[index].lazy = 1LL;
  51. }
  53. if(j <= mid)
  54. update(begin, mid, i, j, index*2, xx);
  55. else if(i > mid)
  56. update(mid+1, end, i, j, index*2+1, xx);
  57. else
  58. update(begin, mid, i, mid, index*2, xx), update(mid+1, end, mid+1, j, index*2+1, xx);
  60. tree[index].val = ((tree[index*2].val%MOD) + (tree[index*2+1].val%MOD))%MOD;
  61. }
  63. long long get(int begin, int end, int i, int j, int index)
  64. {
  65. if(begin >= i and end <= j)
  66. return tree[index].val%MOD;
  67. if(j < begin or i > end) return -1;
  69. long long p1, p2;
  70. int mid=(begin+end)>>1;
  72. if(tree[index].lazy > 1)
  73. {
  74. tree[index*2].val = (tree[index*2].val*tree[index].lazy)%MOD;
  75. tree[index*2+1].val = (tree[index*2+1].val*tree[index].lazy)%MOD;
  76. tree[index].lazy = 1LL;
  77. tree[index].val = (tree[index*2].val+tree[index*2+1].val)%MOD;
  78. }
  80. p1 = get(begin, mid, i, j, index*2);
  81. p2 = get(mid+1, end, i, j, index*2+1);
  83. if(p1 == -1) return p2%MOD;
  84. if(p2 == -1) return p1%MOD;
  85. return (p1+p2)%MOD;
  86. }
  88. void solve()
  89. {
  90. scanf("%d %d", &n, &m);
  91. build(1, n, 1);
  93. for(int i = 0; i < m; i++)
  94. {
  95. scanf("%d", &q);
  96. if(q == 1)
  97. {
  98. scanf("%d %d", &a, &b);
  99. long long ans=get(1, n, a, b, 1)%MOD;
  100. printf("%lld\n", ans);
  101. }
  102. else
  103. {
  104. scanf("%d %d %lld", &a, &b, &x);
  105. upd_value = x;
  106. update(1, n, a, b, 1, x);
  107. /*for(int i = 1; i <= 25; i++)
  108. printf("ID %d ; %d\n", i, tree[i]);*/
  109. }
  110. }
  111. }
  113. int main()
  114. {
  115. solve();
  117. return 0;
  118. }