#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
namespace cst {
const double pi = acos(-1.0);
const int MIN_INT8 = -128;
const int MIN_INT16 = -32768;
const int MIN_INT = -2147483647 - 1;
const long long MIN_LL = -9223372036854775807LL - 1;
const int MAX_INT8 = 127;
const int MAX_INT16 = 32767;
const int MAX_INT = 2147483647;
const long long MAX_LL = 9223372036854775807LL;
}  // namespace cst
namespace t {
template <typename T>
inline const T gcd(T __m, T __n) {
  while (__n != 0) {
    T __t = __m % __n;
    __m = __n;
    __n = __t;
  }
  return __m;
}
template <typename T>
inline const T max(const T &a, const T &b) {
  return a > b ? a : b;
}
template <typename T>
inline const T min(const T &a, const T &b) {
  return a < b ? a : b;
}
template <typename T>
inline const T abs(const T &a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline void in(T &x) {
  register T res = 0;
  register int neg = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) {
    if (c == '-') {
      neg = -1;
    }
  }
  for (; isdigit(c); c = getchar()) {
    res = res * 10 + c - '0';
  }
  x = res * neg;
}
inline int read() {
  register int res = 0, neg = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) {
    if (c == '-') {
      neg = -1;
    }
  }
  for (; isdigit(c); c = getchar()) {
    res = res * 10 + c - '0';
  }
  return res * neg;
}
inline long long read_ll() {
  register long long res = 0, neg = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) {
    if (c == '-') {
      neg = -1;
    }
  }
  for (; isdigit(c); c = getchar()) {
    res = res * 10 + c - '0';
  }
  return res * neg;
}
}  // namespace t
const long long mod = 1e9 + 7;
const long long maxn = 1e5 + 10;
long long cnt = 1, n, m;
long long a[maxn];
inline void ADD(long long &x, long long y) { (x += y) >= mod && (x -= mod); }
struct Matrix {
  long long a[2][2];
  Matrix() {
    a[0][0] = 0;
    a[0][1] = 0;
    a[1][0] = 0;
    a[1][1] = 0;
  }
  inline long long *operator[](long long x) { return a[x]; }
  inline const long long *operator[](long long x) const { return a[x]; }
  inline friend Matrix operator*(Matrix x, Matrix y) {
    Matrix ans;
    for (long long i = 0; i <= cnt; ++i)
      for (long long j = 0; j <= cnt; ++j)
        for (long long k = 0; k <= cnt; ++k)
          ADD(ans[i][j], x[i][k] * y[k][j] % mod);
    return ans;
  }
  inline friend Matrix operator+(Matrix x, Matrix y) {
    Matrix ans;
    for (long long i = 0; i <= cnt; ++i)
      for (long long j = 0; j <= cnt; ++j)
        ADD(ans[i][j], x[i][j]), ADD(ans[i][j], y[i][j]);
    return ans;
  }
  inline friend Matrix operator^(Matrix x, long long b) {
    Matrix ans;
    ans[0][0] = 1;
    ans[0][1] = 0;
    ans[1][0] = 0;
    ans[1][1] = 1;
    for (; b; b >>= 1, x = x * x)
      if (b & 1) ans = ans * x;
    return ans;
  }
};
Matrix fir, bas, emp;
inline void init() {
  bas[0][0] = 1;
  bas[0][1] = 1;
  bas[1][0] = 1;
  bas[1][1] = 0;
  fir[0][0] = 1;
  fir[0][1] = 1;
  fir[1][0] = 0;
  fir[1][1] = 0;
  emp[0][0] = 0;
  emp[0][1] = 0;
  emp[1][0] = 0;
  emp[1][1] = 0;
}
struct seg {
  Matrix tag, num;
} q[maxn * 4];
inline void init(Matrix &a) {
  a[0][0] = 1;
  a[0][1] = 0;
  a[1][0] = 0;
  a[1][1] = 1;
}
inline bool judge(Matrix a) {
  if (a[0][0] != 1) return 0;
  if (a[0][1] != 0) return 0;
  if (a[1][0] != 0) return 0;
  if (a[1][1] != 1) return 0;
  return 1;
}
inline void pushup(long long now) {
  q[now].num = q[now * 2].num + q[now * 2 + 1].num;
}
inline void pushdown(long long now) {
  if (!judge(q[now].tag)) {
    Matrix cur = q[now].tag;
    q[now * 2].num = q[now * 2].num * cur;
    q[now * 2 + 1].num = q[now * 2 + 1].num * cur;
    q[now * 2].tag = q[now * 2].tag * cur;
    q[now * 2 + 1].tag = q[now * 2 + 1].tag * cur;
    init(q[now].tag);
  }
}
void build(long long now, long long l, long long r) {
  init(q[now].tag);
  if (l == r) {
    init(q[now].tag);
    q[now].num = fir * (bas ^ (a[l] - 1));
    return;
  }
  long long mid = (l + r) / 2;
  build(now * 2, l, mid);
  build(now * 2 + 1, mid + 1, r);
  pushup(now);
}
void change(long long now, long long l, long long r, long long cl, long long cr,
            Matrix k) {
  if (r < cl || l > cr) return;
  if (l >= cl && r <= cr) {
    q[now].num = q[now].num * k;
    q[now].tag = q[now].tag * k;
    return;
  }
  pushdown(now);
  long long mid = (l + r) / 2;
  change(now * 2, l, mid, cl, cr, k);
  change(now * 2 + 1, mid + 1, r, cl, cr, k);
  pushup(now);
}
Matrix query(long long now, long long l, long long r, long long cl,
             long long cr) {
  if (r < cl || l > cr) return emp;
  if (l >= cl && r <= cr) return q[now].num;
  pushdown(now);
  long long mid = (l + r) / 2;
  return query(now * 2, l, mid, cl, cr) +
         query(now * 2 + 1, mid + 1, r, cl, cr);
}
int main() {
  n = t::read_ll(), m = t::read_ll();
  init();
  for (long long i = 1; i <= n; ++i) {
    a[i] = t::read_ll();
  }
  build(1, 1, n);
  for (long long i = 1, opt, l, r, x; i <= m; ++i) {
    t::in(opt), t::in(l), t::in(r);
    if (opt == 1) {
      t::in(x);
      change(1, 1, n, l, r, bas ^ x);
    } else
      printf("%lld\n", query(1, 1, n, l, r)[0][1] % mod);
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

Sasha has an array of integers a1, a2, ..., an. You have to perform m queries. There might be queries of two types:

  1. 1 l r x — increase all integers on the segment from l to r by values x; 
  2. 2 l r — find <image>, where f(x) is the x-th Fibonacci number. As this number may be large, you only have to find it modulo 109 + 7. 



In this problem we define Fibonacci numbers as follows: f(1) = 1, f(2) = 1, f(x) = f(x - 1) + f(x - 2) for all x > 2.

Sasha is a very talented boy and he managed to perform all queries in five seconds. Will you be able to write the program that performs as well as Sasha?

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of elements in the array and the number of queries respectively.

The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Then follow m lines with queries descriptions. Each of them contains integers tpi, li, ri and may be xi (1 ≤ tpi ≤ 2, 1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 109). Here tpi = 1 corresponds to the queries of the first type and tpi corresponds to the queries of the second type.

It's guaranteed that the input will contains at least one query of the second type.

Output

For each query of the second type print the answer modulo 109 + 7.

Examples

Input

5 4
1 1 2 1 1
2 1 5
1 2 4 2
2 2 4
2 1 5


Output

5
7
9

Note

Initially, array a is equal to 1, 1, 2, 1, 1.

The answer for the first query of the second type is f(1) + f(1) + f(2) + f(1) + f(1) = 1 + 1 + 1 + 1 + 1 = 5. 

After the query 1 2 4 2 array a is equal to 1, 3, 4, 3, 1.

The answer for the second query of the second type is f(3) + f(4) + f(3) = 2 + 3 + 2 = 7.

The answer for the third query of the second type is f(1) + f(3) + f(4) + f(3) + f(1) = 1 + 2 + 3 + 2 + 1 = 9.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
namespace cst {
const double pi = acos(-1.0);
const int MIN_INT8 = -128;
const int MIN_INT16 = -32768;
const int MIN_INT = -2147483647 - 1;
const long long MIN_LL = -9223372036854775807LL - 1;
const int MAX_INT8 = 127;
const int MAX_INT16 = 32767;
const int MAX_INT = 2147483647;
const long long MAX_LL = 9223372036854775807LL;
}  // namespace cst
namespace t {
template <typename T>
inline const T gcd(T __m, T __n) {
  while (__n != 0) {
    T __t = __m % __n;
    __m = __n;
    __n = __t;
  }
  return __m;
}
template <typename T>
inline const T max(const T &a, const T &b) {
  return a > b ? a : b;
}
template <typename T>
inline const T min(const T &a, const T &b) {
  return a < b ? a : b;
}
template <typename T>
inline const T abs(const T &a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline void in(T &x) {
  register T res = 0;
  register int neg = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) {
    if (c == '-') {
      neg = -1;
    }
  }
  for (; isdigit(c); c = getchar()) {
    res = res * 10 + c - '0';
  }
  x = res * neg;
}
inline int read() {
  register int res = 0, neg = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) {
    if (c == '-') {
      neg = -1;
    }
  }
  for (; isdigit(c); c = getchar()) {
    res = res * 10 + c - '0';
  }
  return res * neg;
}
inline long long read_ll() {
  register long long res = 0, neg = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) {
    if (c == '-') {
      neg = -1;
    }
  }
  for (; isdigit(c); c = getchar()) {
    res = res * 10 + c - '0';
  }
  return res * neg;
}
}  // namespace t
const long long mod = 1e9 + 7;
const long long maxn = 1e5 + 10;
long long cnt = 1, n, m;
long long a[maxn];
inline void ADD(long long &x, long long y) { (x += y) >= mod && (x -= mod); }
struct Matrix {
  long long a[2][2];
  Matrix() {
    a[0][0] = 0;
    a[0][1] = 0;
    a[1][0] = 0;
    a[1][1] = 0;
  }
  inline long long *operator[](long long x) { return a[x]; }
  inline const long long *operator[](long long x) const { return a[x]; }
  inline friend Matrix operator*(Matrix x, Matrix y) {
    Matrix ans;
    for (long long i = 0; i <= cnt; ++i)
      for (long long j = 0; j <= cnt; ++j)
        for (long long k = 0; k <= cnt; ++k)
          ADD(ans[i][j], x[i][k] * y[k][j] % mod);
    return ans;
  }
  inline friend Matrix operator+(Matrix x, Matrix y) {
    Matrix ans;
    for (long long i = 0; i <= cnt; ++i)
      for (long long j = 0; j <= cnt; ++j)
        ADD(ans[i][j], x[i][j]), ADD(ans[i][j], y[i][j]);
    return ans;
  }
  inline friend Matrix operator^(Matrix x, long long b) {
    Matrix ans;
    ans[0][0] = 1;
    ans[0][1] = 0;
    ans[1][0] = 0;
    ans[1][1] = 1;
    for (; b; b >>= 1, x = x * x)
      if (b & 1) ans = ans * x;
    return ans;
  }
};
Matrix fir, bas, emp;
inline void init() {
  bas[0][0] = 1;
  bas[0][1] = 1;
  bas[1][0] = 1;
  bas[1][1] = 0;
  fir[0][0] = 1;
  fir[0][1] = 1;
  fir[1][0] = 0;
  fir[1][1] = 0;
  emp[0][0] = 0;
  emp[0][1] = 0;
  emp[1][0] = 0;
  emp[1][1] = 0;
}
struct seg {
  Matrix tag, num;
} q[maxn * 4];
inline void init(Matrix &a) {
  a[0][0] = 1;
  a[0][1] = 0;
  a[1][0] = 0;
  a[1][1] = 1;
}
inline bool judge(Matrix a) {
  if (a[0][0] != 1) return 0;
  if (a[0][1] != 0) return 0;
  if (a[1][0] != 0) return 0;
  if (a[1][1] != 1) return 0;
  return 1;
}
inline void pushup(long long now) {
  q[now].num = q[now * 2].num + q[now * 2 + 1].num;
}
inline void pushdown(long long now) {
  if (!judge(q[now].tag)) {
    Matrix cur = q[now].tag;
    q[now * 2].num = q[now * 2].num * cur;
    q[now * 2 + 1].num = q[now * 2 + 1].num * cur;
    q[now * 2].tag = q[now * 2].tag * cur;
    q[now * 2 + 1].tag = q[now * 2 + 1].tag * cur;
    init(q[now].tag);
  }
}
void build(long long now, long long l, long long r) {
  init(q[now].tag);
  if (l == r) {
    init(q[now].tag);
    q[now].num = fir * (bas ^ (a[l] - 1));
    return;
  }
  long long mid = (l + r) / 2;
  build(now * 2, l, mid);
  build(now * 2 + 1, mid + 1, r);
  pushup(now);
}
void change(long long now, long long l, long long r, long long cl, long long cr,
            Matrix k) {
  if (r < cl || l > cr) return;
  if (l >= cl && r <= cr) {
    q[now].num = q[now].num * k;
    q[now].tag = q[now].tag * k;
    return;
  }
  pushdown(now);
  long long mid = (l + r) / 2;
  change(now * 2, l, mid, cl, cr, k);
  change(now * 2 + 1, mid + 1, r, cl, cr, k);
  pushup(now);
}
Matrix query(long long now, long long l, long long r, long long cl,
             long long cr) {
  if (r < cl || l > cr) return emp;
  if (l >= cl && r <= cr) return q[now].num;
  pushdown(now);
  long long mid = (l + r) / 2;
  return query(now * 2, l, mid, cl, cr) +
         query(now * 2 + 1, mid + 1, r, cl, cr);
}
int main() {
  n = t::read_ll(), m = t::read_ll();
  init();
  for (long long i = 1; i <= n; ++i) {
    a[i] = t::read_ll();
  }
  build(1, 1, n);
  for (long long i = 1, opt, l, r, x; i <= m; ++i) {
    t::in(opt), t::in(l), t::in(r);
    if (opt == 1) {
      t::in(x);
      change(1, 1, n, l, r, bas ^ x);
    } else
      printf("%lld\n", query(1, 1, n, l, r)[0][1] % mod);
  }
  return 0;
}

```