#include <bits/stdc++.h>   using namespace std;   int mod = (int)1e9 + 7;   struct matrix {     int A[2][2] = {0};     matrix operator*(matrix B) {       matrix C;       for (int i = 0; i < 2; i++)         for (int j = 0; j < 2; j++)           for (int k = 0; k < 2; k++)             C[i][j] = (C[i][j] + 1ll * A[i][k] * B[k][j]) % mod;       return C;     }     matrix operator+(matrix B) {       matrix C;       for (int i = 0; i < 2; i++)         for (int j = 0; j < 2; j++) C[i][j] = (A[i][j] + B[i][j]) % mod;       return C;     }     matrix pow(int n) {       matrix B, C = *this;       for (int i = 0; i < 2; i++) B[i][i] = 1;       while (n) {         if (n & 1) B = B * C;         C = C * C;         n >>= 1;       }       return B;     }     int *operator[](int i) { return A[i]; }   };   matrix fib;   struct segment_tree {     struct node {       node *node_l, *node_r;       int l, r;       matrix sum, mul;     } * root;     node *build(vector<int> &a, int l, int r) {       node *res = new node;       res->l = l;       res->r = r;       res->mul[0][0] = res->mul[1][1] = 1;       if (l == r) {         res->sum = fib.pow(a[l]);         res->node_l = res->node_r = nullptr;       } else {         int m = (l + r) >> 1;         res->node_l = build(a, l, m);         res->node_r = build(a, m + 1, r);         res->sum = res->node_l->sum + res->node_r->sum;       }       return res;     }     void build(vector<int> &a) { root = build(a, 0, a.size() - 1); }     void push(node *root) {       if (root->mul[1][0] + root->mul[0][0] + root->mul[0][1] + root->mul[1][1] ==           2)         return;       if (root->node_l) {         root->node_l->mul = root->node_l->mul * root->mul;         root->node_l->sum = root->node_l->sum * root->mul;       }       if (root->node_r) {         root->node_r->mul = root->node_r->mul * root->mul;         root->node_r->sum = root->node_r->sum * root->mul;       }       root->mul[0][0] = root->mul[1][1] = 1;       root->mul[1][0] = root->mul[0][1] = 0;     }     void update(node *root, int l, int r) {       if (root->l > r || root->r < l) return;       if (root->l >= l && root->r <= r) {         root->sum = root->sum * fib;         root->mul = root->mul * fib;       } else {         push(root);         update(root->node_l, l, r);         update(root->node_r, l, r);         root->sum = root->node_l->sum + root->node_r->sum;       }     }     void update(int l, int r) { update(root, l, r); }     matrix query(node *root, int l, int r) {       push(root);       if (root->l > r || root->r < l) return matrix();       if (root->l >= l && root->r <= r) return root->sum;       return query(root->node_l, l, r) + query(root->node_r, l, r);     }     matrix query(int l, int r) { return query(root, l, r); }   };   int main() {     fib[0][1] = fib[1][0] = fib[0][0] = 1;     int n, m;     scanf( %d %d , &n, &m);     vector<int> v(n);     for (int &p : v) scanf( %d , &p);     segment_tree sg;     sg.build(v);     for (int i = 0; i < m; i++) {       int t, l, r;       scanf( %d %d %d , &t, &l, &r);       l--, r--;       if (t == 1) {         int x;         scanf( %d , &x);         matrix tmp = fib;         fib = fib.pow(x);         sg.update(l, r);         fib = tmp;       } else {         printf( %d n , sg.query(l, r)[0][1]);       }     }   }   