Rồng Rắn Lên Mây (Tháng Bảy Version)


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

"Rồng rắn lên mây

Có cây núc nác

Có nhà điểm binh

Hỏi ông Thầy thuốc có nhà hay không?"

Từ xa xưa, trùng tang luôn là một trong những hiện tượng khiến cho con người ta kinh hãi nhất. Một trong những cách giải nghĩa bài đồng dao Rồng Rắn Lên Mây là về hiện tượng này.

Già trẻ lớn bé của dòng họ X nọ đang lũ lượt kéo đến nhà một ông thầy chuyên bắt trùng nổi tiếng trong vùng. Nhà ông thầy ở cách xa làng mạc, ông sống ẩn cư kế bên một dãy núi. Khu nhà được xây theo kiến trúc 3 gian truyền thống, nhà chính đặt một bàn thờ trang nghiêm. Hai bên hữu tả là phòng ăn, bếp và phòng nghỉ, phòng chế thuốc của ông. Giữa khoảng sân vườn mọc lên một cây núc nác, xung quanh là những loại dược liệu quý. Được biết, ông thầy này vừa có khả năng tâm linh, vừa biết bốc thuốc. Vì thế, những người đến đây đều cảm giác được sự trong lành, mùi hương thoang thoảng của thảo mộc. Tuy nhiên, ai cũng truyền tai nhau cảm giác ớn lạnh ở phía sau gáy mỗi khi nhìn vào gian nhà chính.

Đây là lần thứ năm họ đến hỏi thăm ông thầy có ở nhà hay không? Những lần trước họ đến, ông thầy đều đang hái thuốc trên núi. Nhưng lần này, họ đã gặp may, ông thầy ở nhà.

...

Mới năm ngoái, anh Y nhà bà Z trong họ đang sống khỏe mạnh thì bỗng một ngày lên cơn đột quỵ. Vợ con anh, mẹ già anh đau đớn khôn xiết khi người trụ cột chính đã rời xa. Người trong làng tốt bụng hùn góp tiền lo ma chay cho anh. Ngày đưa ma, một đàn quạ cứ bay theo đoàn người khiến ai cũng cảm thấy bất an. Đến đêm hôm đó, chúng thi nhau kêu lên những âm thanh ám ảnh khắp ngôi làng.

Chỉ sau 1 tuần, bà Z cũng đi theo anh Y do một tai nạn ở gần nhà. Con cháu bà ai cũng hoang mang lo lắng, khi trên đầu đã phải mang hai dải băng trắng. Bẵng đi mấy tháng, một người cháu trong họ đang trú mưa thì bị sét đánh dưới gốc cây. Chao ôi, chỉ chưa đầy nửa năm, cả họ đã có hơn 3 người đi. Mọi người phải họp gấp.

"Hôm anh Y mất, có ai đi xem ngày chưa?", một người lên tiếng.

"Hôm đó bất ngờ quá nên chưa ai đi xem tử tế", người khác đáp lời.

"Ôi dồi ôi, sao lại thế!", ông trưởng họ đáp lại.

Bỗng phía sau, một người thốt lên: "Dời ơi, thằng Y, nó mất vào giờ trùng! Tôi mới bấm ra, là trùng liên táng, là chết liên tục cả họ đấy!".

Lúc này, nhìn mặt ai cũng căng thẳng, bọn trẻ con thấy người lớn lo lắng như vậy thì bắt đầu òa khóc lên. Ai ai lúc này cũng mang trong mình một gánh nặng.

"Thế bây giờ phải làm sao?", một người mếu máo hỏi.

"Đến tìm gặp ông thầy thuốc ở cạnh núi A", ông trưởng họ nói dõng dạc.

...

Ông thầy nghe xong đầu đuôi câu chuyện, tay bấm tính gì đó, rồi liền nói: "Oithoichet! Tắc trách quá, muộn quá, sao lại tới muộn quá!"

Ông thầy sau đó đưa ra kế sách giúp dòng họ X giải quyết. Nhưng ông đưa ra một điều kiện: "Tôi cần một vài đứa con nuôi để kế nghiệp bốc thuốc này." Cả đang đang rối ren nên đồng ý ngay với thầy. Ông sau đó lập một đàn tế, áp hồn người mất lên chùa nhốt vong. Sau ba năm, không thấy sự gì nữa, mới được đưa về nhà thờ cúng.

Khi mọi chuyện đã qua thì ông gửi thư thúc dục điều mà cả họ đã hứa. Ông sai âm binh đến từng nhà để nhắc nhở trong từng giấc chiêm bao của người họ X. Dòng họ hiện tại có \(10^N\) đứa trẻ. Họ đánh số mỗi đứa trẻ từ 0 đến \(10^N-1\). Số lượng quá lớn, họ không thể biết ông thầy muốn bắt ai, chỉ có thể dựa vào các gợi ý để đưa ra các phương án. Họ đã kịp tổng hợp lại được \(M\) gợi ý trong từng giấc mơ. Các gợi ý được sắp xếp theo thứ tự thời gian. Mỗi gợi ý có hai dạng:

  • Y l r d: Chữ số ở vị trí thứ \(l\) đến thứ \(r\) trong mã số của đứa trẻ bị bắt là \(d\).
  • N l r d: Chữ số ở vị trí thứ \(l\) đến thứ \(r\) trong mã số của đứa trẻ bị bắt không phải là \(d\).

Lưu ý: Có thể xem việc đánh vị trí cho chữ số là từ trái sang phải. Ví dụ chữ số thứ 3 của số 4567 là 5.

Hãy giúp người họ X xác định được số đứa trẻ có thể bị bắt theo gợi ý sau mỗi giấc mơ!

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên dương \(N, M \ (1 \le N \le 10^5; 1\le M \le 10^4)\);
  • \(M\) dòng tiếp theo, mỗi dòng chứa các gợi ý như trên \((1\le l \le r\le N; 0\le d \le 9)\).

Kết quả

  • In trên \(M\) dòng, mỗi dòng một số nguyên là số lượng đứa trẻ có thể bị bắt sau gợi ý tương ứng, chia lấy dư cho \(10^9+7\).

Chấm điểm

  • Subtask 1 (50%): \(N, M \le 10^3\).
  • Subtask 2 (50%): Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

4 2
Y 1 1 3
N 3 4 3

output

1000
810
Ví dụ 2

input

3 4
Y 1 2 0
N 2 3 1
Y 3 3 2
N 1 1 7

output

3
Ví dụ 3

input

2 4
Y 1 1 0
N 1 1 1
Y 1 2 2
N 1 2 7

output

3

Giải thích

Ở ví dụ 1, các đứa trẻ được đánh số từ 0000 đến 9999.

  • Gợi ý 1, chữ số ở vị trí 1 là 3, những đứa trẻ có thể bị bắt có dạng \(xxx3\), có \(10\times 10 \times 10 = 1000\) số như vậy.
  • Gợi ý 2, chữ số ở vị trí 3 đến 4 không phải 3, có \(9 \times 9 \times 10 = 810\) số như vậy.

Comments

There are no comments at the moment.