题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIV Olimpiada Informatyczna — II etap Zawody sportowe

在一次体育比赛中，来自 $n$ 个不同国家的 $n$ 名选手展开角逐。每位选手由本国的 $n$ 名记者之一进行报道，记者会说明自家选手的名次。然而，部分记者因情绪激动，未能准确记住选手的名次，只能提供选手可能的两个名次。

请根据记者的报道，判断是否能唯一确定比赛的排名（不允许并列名次）。若可以，输出排名；否则，计算可能的排名数量。

输入格式

第一行包含一个正整数 $n$，表示参赛国家的数量。

接下来的 $n$ 行描述记者的报道，第 $i$ 行表示第 $i$ 国记者的报道：

• 若记者确定选手名次，报道为字母 T 后跟一个整数 $a_i$ $(1 \leq a_i \leq n)$，表示第 $i$ 国选手的名次。
• 若记者不确定，报道为字母 N 后跟两个不同整数 $a_{i,1}, a_{i,2}$ $(1 \leq a_{i,j} \leq n)$，表示第 $i$ 国选手名次为 $a_{i,1}$ 或 $a_{i,2}$。

输出格式

若记者报道能唯一确定比赛排名，输出第一行包含字符串 TAK，接下来的 $n$ 行每行一个整数，第 $i$ 行表示第 $i$ 国选手的名次。

若报道矛盾或排名不唯一，输出第一行包含字符串 NIE，第二行输出可能排名的数量对 $1000000007$ 取模的结果。

3
N 2 3
T 3
N 2 1

TAK
2
3
1

3
N 2 1
T 3
N 2 1

NIE
2

提示

附加样例

1. $n=5$，每位记者不确定，报道矛盾。
2. $n=10$，每位记者不确定，有 $32$ 种可能排名。
3. $n=1000000$，每位记者确定（$a_i=i$），答案为 TAK。

详细子任务附加限制及分值如下表所示。