숫자 이어 붙이기
면접 대비시간 제한1초메모리 제한512 MB
트리에서 두 집 사이 경로의 문 번호를 방문 순서대로 이어 붙인 수를 10^9+7로 나눈 나머지로 각 질의마다 구합니다.
문제
철수는 수를 이어 붙이는 놀이를 좋아한다. 1과 2를 이어 붙이면 12가 되고, 17과 13을 이어 붙이면 1713이 된다. 100과 1000을 이어 붙이면 1001000이 된다. 1과 2를 이어 붙이되 순서를 반대로 하면, 즉 2와 1을 이어 붙이면 21이 된다. 같은 두 수라도 이어 붙이는 순서에 따라 값이 달라진다.
철수가 사는 마을에는 집이 여러 채 있고, 각 집에는 1부터 N까지 번호가 붙어 있다. 두 집 사이에 있는 도로를 따라 서로 이동할 수 있다. 도로는 총 N-1개이며, i번째 도로는 a_i번 집과 b_i번 집을 잇는다. 집과 도로는 트리 형태를 이룬다. 즉, 어느 집에서 출발하더라도 몇 개의 도로를 거쳐 다른 모든 집에 갈 수 있고, 같은 집을 두 번 방문하지 않는 경로는 하나뿐이다.
각 집의 대문에는 수가 적혀 있다. 철수는 Q번 놀이를 한다. i번째 놀이에서는 x_i번 집에서 출발해 y_i번 집까지 이동하면서, 경로에 있는 집들의 대문에 적힌 수를 방문한 순서대로 이어 붙인다. x_i = y_i이면 x_i번 집의 대문에 적힌 수가 답이다. 철수는 놀이가 끝날 때마다 이어 붙인 수의 값을 알고 싶어 한다. 수가 매우 커질 수 있으므로, 값을 로 나눈 나머지를 출력한다.
입력
첫 번째 줄에는 집의 개수 N과 놀이 횟수 Q가 주어진다.
두 번째 줄에는 N개 집의 대문에 적힌 수 A_i가 공백을 사이에 두고 순서대로 주어진다.
세 번째 줄부터 N+1번째 줄까지는 도로 정보가 주어진다. 2+i번째 줄에는 i번째 도로가 잇는 두 집의 번호 a_i, b_i가 공백을 사이에 두고 주어진다.
N+2번째 줄부터 N+Q+1번째 줄까지는 놀이 정보가 주어진다. N+i+1번째 줄에는 i번째 놀이를 시작할 집의 번호 x_i와 끝낼 집의 번호 y_i가 공백을 사이에 두고 주어진다.
출력
첫 번째 줄부터 Q번째 줄까지 출력한다. i번째 줄에는 i번째 놀이의 결과를 로 나눈 나머지를 출력한다.
제한
- ()