Nhắc lại Fn là số fibonacci thứ n với F1 = F2 = 1.

Cho mảng a có n phần tử và q truy vấn có một trong 2 dạng sau đây:

• 1 l r, cộng thêm giá trị F(i-l+1) với mỗi phần tử l ≤ i ≤ r.

• 2 l r, in ra tổng của các giá trị a[i] với i từ l đến r chia dư cho 10^7 + 9.

Input:

• Dòng đầu tiên gồm 2 số 1 ≤ n, q ≤ 300000.

• Dòng tiếp theo gồm n số tự nhiên của mảng a (1 ≤ ai ≤ 10^().

Output:

• In ra kết quả của mỗi truy vấn 2.

Sample Test

Input:

4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3

Output:

17
12