“터져라 리얼! 터져라 시놉스! Van!shment th!s world!!!”

“케루빔의 영창! 세라핌의 강림! Physical linkage!!”

지금 이 순간, 성스러운 어둠의 힘이 담긴 사왕진안이자 각종 사역마들을 사역하는 ‘사왕진안’ 김기범은 자신의 오랜 숙적인 마법마왕소녀 소피아링•SP•사탄•7세 박종경과 긴 악연의 끝을 내기 위해 최후의 결전을 치르게 되었다. 

김기범은 자신의 최강의 기술인 [스파이더 인 미러]를 사용하기 위해 투기장 곳곳에 떨어진 마도석을 모아야 한다. 그러나, [스파이더 인 미러]는 정확한 마력량을 요구하며, 시시각각 변하는 전장에서 모든 마도석을 보기는 어렵다. 

사왕진안 김기범은 총 q개의 전략을 짜기로 했다. 편의상 마도석에 1번부터 n번까지 번호를 매기자. 

하나의 전략은 세 개의 정수 x,y,z로 표현할 수 있으며, 그에 대해 x번째 마도석과 y번째 마도석까지의 마도석을 적절히 골라 그 마력의 총합이 z가 되도록 하는 경우의 수를 알아내야 한다.

첫 줄에 n,q(n,q<=1000)가 주어진다. 이는 각각 마도석의 개수, 전략의 개수를 의미한다.

두 번째 줄에 a_1, ...a_n(a_i>=0, 모든 마력의 합은 1000을 넘지 않는다)가 주어진다. 이는 각각 I번째 마도석의 마력량을 의미한다.

세 번째 줄부터 n+2번째 줄에 x,y,z가 주어지는데 i번째 줄에는 x_i-2, y_i-2, z_i-2(1<=x_i-2, y_i-2<=n, 0<=z_i-2<=1000)가 주어진다. 이는 위에서 설명한 값들을 의미한다.

각 전략에 대해 마력의 총합이 z가 되는 경우의 수를 10억7로 나눈 나머지를 한 줄에 하나씩 출력한다.