/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
この問題は output-only です。
符号無し 64 bit 整数の加算・乗算・ 998244353 を除数とする modulo 演算ができるプログラミング言語があります。
この言語を用いて \text{mod }1000000007 における乗算を行うプログラムを作成してください。
厳密に説明すると、0 以上 1000000006 以下の整数 a,b が与えられたときに a \times b \bmod{1000000007} を計算するプログラムを、以下の 仕様・形式 に従って作成してください。
プログラムの仕様
このプログラムでは、英大文字で表される A, B, \dots, Z の 26 個の 変数 を扱うことが出来る。
各変数は 0 以上 2^{64} 未満の整数値 (以下 符号無し 64 bit 整数 と表記) を保持することが出来る。
プログラムの実行開始時点で、A には整数 a が、B には整数 b が、それ以外の変数には 0 が代入されている。
プログラムの実行終了時点で変数 C に a \times b \bmod{1000000007} が保持されている必要がある。
プログラムの形式
プログラムの 1 行目にはプログラムの命令数を表す整数 N (1 \leq N \leq 100) が書かれる。
プログラムの 2 行目から N + 1 行目には N 個の命令が書かれる。命令は上から下に順次実行される。
命令は次の 3 つのいずれかである。
add x y z- x に (y + z) \bmod{2^{64}} を代入する。ここでは x は変数、y, z は変数または符号無し 64 bit 整数である。
mul x y z- x に y \times z \bmod{2^{64}} を代入する。ここでは x は変数、y, z は変数または符号無し 64 bit 整数である。
rem x y- x に y \bmod{998244353} を代入する。ここでは x は変数、y は変数または符号無し 64 bit 整数である。
入力
標準入力から与えられる入力は空である。
出力
問題文に書かれている仕様・形式に従ったプログラムを出力せよ。
ジャッジ
提出されたプログラムの形式が誤っていた場合、ジャッジの判定は不定である。
提出されたプログラムの形式が正しい場合、ジャッジは 1 ケース毎に 10^4 個の整数の組 (a, b) (0 \leq a, b \leq 1000000006) に対してプログラムを独立に実行する。(整数の組はジャッジ側があらかじめ用意したものであり、テストケース毎に固定である。)
全ての (a, b) の組に対して実行終了時に変数 C に a \times b \bmod{1000000007} が保持されている場合、ジャッジの判定は AC となる。そうでない場合は WA となる。
出力例
正しい形式で書かれたプログラムの例を示します。(このプログラムは仕様を満たしていないため、提出しても WA となります。)
5 mul C A B rem C C add A A 10 add D 2 B add E 1 0
このプログラムの実行終了時点で各変数に代入されている値は次の通りです。
- A : a + 10
- B : b
- C : a \times b \bmod{998244353}
- D : b + 2
- E : 1
- それ以外の変数 : 0
Score : 1000 points
Problem Statement
This problem is output-only.
We have a programming language equipped with the following operations of unsigned 64-bit integers: addition, multiplication, and a modulo operation where the divisor is 998244353.
Write a program that performs multiplication modulo 1000000007 in this language.
More formally, write a program that receives integers a and b between 0 and 1000000006 and computes a \times b \bmod{1000000007} under the following Specification and Format.
Specification
The program can handle 26 variables represented by uppercase English letters: A, B, \dots, Z.
Each variable can hold an integer value between 0 and 2^{64}-1 (inclusive). Below, such a value is called unsigned 64-bit integer.
At the start of the execution of the program, A is assigned an integer a, B is assigned an integer b, and the other variables are assigned 0.
At the end of the execution, C must hold a \times b \bmod{1000000007}.
Format
The 1-st line of the program contains an integer N (1 \leq N \leq 100) representing the number of instructions in the program.
The 2-nd through (N + 1)-th lines contain N instructions. The instructions are executed one by one from top to bottom.
Each instruction is in one of the following three forms.
add x y z- Assign (y + z) \bmod{2^{64}} to x, where x is a variable, and each of y and z is a variable or an unsigned 64-bit integer.
mul x y z- Assign (y \times z) \bmod{2^{64}} to x, where x is a variable, and each of y and z is a variable or an unsigned 64-bit integer.
rem x y- Assign y \bmod{998244353} to x, where x is a variable, and y is a variable or an unsigned 64-bit integer.
Input
The input given from Standard Input is empty.
Output
Print a program under the Specification and Format.
Judging
If the submitted program is malformed, the verdict will be indeterminate.
If the submitted program is well-formed, for each test case, the judge will execute it against 10^4 pairs of integers (a, b) (0 \leq a, b \leq 1000000006) independently. (These pairs are prepared beforehand and constant for each test case.)
If the variable C holds a \times b \bmod{1000000007} at the end of the execution for all pairs (a, b), the verdict will be AC; otherwise, it will be WA.
Sample Output
Here is an example of a well-formed program. (The Specification is not satisfied, so it will be judged as WA if submitted.)
5 mul C A B rem C C add A A 10 add D 2 B add E 1 0
At the end of the execution of this program, the variables will hold the following values.
- A: a + 10
- B: b
- C: a \times b \bmod{998244353}
- D: b + 2
- E: 1
- The others: 0