fft.koopa

decl @getint(): i32
decl @getch(): i32
decl @getarray(*i32): i32
decl @putint(i32)
decl @putch(i32)
decl @putarray(i32, *i32)
decl @starttime()
decl @stoptime()
global @d = alloc i32, zeroinit

fun @multiply(@a_0: i32, @b_0: i32): i32 {
%LLB_7:
	%a_0 = alloc i32
	store @a_0, %a_0
	%b_0 = alloc i32
	store @b_0, %b_0
	%0 = load %b_0
	%1 = eq %0, 0
	br %1, %LLB_0, %LLB_1

%LLB_0:
	ret 0

%LLB_1:
	%2 = load %b_0
	%3 = eq %2, 1
	br %3, %LLB_2, %LLB_3

%LLB_2:
	%4 = load %a_0
	%5 = mod %4, 998244353
	ret %5

%LLB_3:
	@cur_0 = alloc i32
	%6 = load %a_0
	%8 = load %b_0
	%9 = div %8, 2
	%10 = call @multiply(%6, %9)
	store %10, @cur_0
	%11 = load @cur_0
	%12 = load @cur_0
	%13 = add %11, %12
	%14 = mod %13, 998244353
	store %14, @cur_0
	%15 = load %b_0
	%16 = mod %15, 2
	%17 = eq %16, 1
	br %17, %LLB_4, %LLB_5

%LLB_4:
	%18 = load @cur_0
	%19 = load %a_0
	%20 = add %18, %19
	%21 = mod %20, 998244353
	ret %21

%LLB_5:
	%22 = load @cur_0
	ret %22

%LLB_6:
	ret 0
}


fun @power(@a_1: i32, @b_1: i32): i32 {
%LLB_13:
	%a_1 = alloc i32
	store @a_1, %a_1
	%b_1 = alloc i32
	store @b_1, %b_1
	%23 = load %b_1
	%24 = eq %23, 0
	br %24, %LLB_8, %LLB_9

%LLB_8:
	ret 1

%LLB_9:
	@cur_1 = alloc i32
	%25 = load %a_1
	%27 = load %b_1
	%28 = div %27, 2
	%29 = call @power(%25, %28)
	store %29, @cur_1
	%30 = load @cur_1
	%31 = load @cur_1
	%32 = call @multiply(%30, %31)
	store %32, @cur_1
	%33 = load %b_1
	%34 = mod %33, 2
	%35 = eq %34, 1
	br %35, %LLB_10, %LLB_11

%LLB_10:
	%36 = load @cur_1
	%37 = load %a_1
	%38 = call @multiply(%36, %37)
	ret %38

%LLB_11:
	%39 = load @cur_1
	ret %39

%LLB_12:
	ret 0
}

global @temp = alloc [i32, 2097152], zeroinit
global @a = alloc [i32, 2097152], zeroinit
global @b = alloc [i32, 2097152], zeroinit
global @c = alloc [i32, 2097152], zeroinit

fun @MemMove(@dst_0: *i32, @dst_pos_0: i32, @src_0: *i32, @len_0: i32): i32 {
%LLB_18:
	%dst_0 = alloc *i32
	store @dst_0, %dst_0
	%dst_pos_0 = alloc i32
	store @dst_pos_0, %dst_pos_0
	%src_0 = alloc *i32
	store @src_0, %src_0
	%len_0 = alloc i32
	store @len_0, %len_0
	@i_0 = alloc i32
	store 0, @i_0
	jump %LLB_16

%LLB_16:
	%40 = load @i_0
	%41 = load %len_0
	%42 = lt %40, %41
	br %42, %LLB_17, %LLB_15

%LLB_17:
	%43 = load %dst_pos_0
	%44 = load @i_0
	%45 = add %43, %44
	%46 = load %dst_0
	%47 = getptr %46, %45
	%48 = load @i_0
	%49 = load %src_0
	%50 = getptr %49, %48
	%51 = load %50
	store %51, %47
	jump %LLB_14

%LLB_14:
	%52 = load @i_0
	%53 = add %52, 1
	store %53, @i_0
	jump %LLB_16

%LLB_15:
	%54 = load %len_0
	%55 = sub %54, 1
	ret %55
}


fun @fft(@arr_0: *i32, @begin_pos_0: i32, @n_0: i32, @w_0: i32): i32 {
%LLB_32:
	%arr_0 = alloc *i32
	store @arr_0, %arr_0
	%begin_pos_0 = alloc i32
	store @begin_pos_0, %begin_pos_0
	%n_0 = alloc i32
	store @n_0, %n_0
	%w_0 = alloc i32
	store @w_0, %w_0
	%56 = load %n_0
	%57 = eq %56, 1
	br %57, %LLB_19, %LLB_20

%LLB_19:
	ret 1

%LLB_20:
	@i_1 = alloc i32
	store 0, @i_1
	jump %LLB_23

%LLB_23:
	%58 = load @i_1
	%59 = load %n_0
	%60 = lt %58, %59
	br %60, %LLB_24, %LLB_22

%LLB_24:
	%61 = load @i_1
	%62 = mod %61, 2
	%63 = eq %62, 0
	br %63, %LLB_25, %LLB_26

%LLB_25:
	%65 = load @i_1
	%66 = div %65, 2
	%67 = getelemptr @temp, %66
	%68 = load @i_1
	%69 = load %begin_pos_0
	%70 = add %68, %69
	%71 = load %arr_0
	%72 = getptr %71, %70
	%73 = load %72
	store %73, %67
	jump %LLB_27

%LLB_26:
	%75 = load %n_0
	%76 = div %75, 2
	%78 = load @i_1
	%79 = div %78, 2
	%80 = add %76, %79
	%81 = getelemptr @temp, %80
	%82 = load @i_1
	%83 = load %begin_pos_0
	%84 = add %82, %83
	%85 = load %arr_0
	%86 = getptr %85, %84
	%87 = load %86
	store %87, %81
	jump %LLB_27

%LLB_27:
	%88 = load @i_1
	%89 = add %88, 1
	store %89, @i_1
	jump %LLB_21

%LLB_21:
	%90 = load @i_1
	%91 = add %90, 1
	store %91, @i_1
	jump %LLB_23

%LLB_22:
	%92 = load %arr_0
	%93 = load %begin_pos_0
	%94 = getelemptr @temp, 0
	%95 = load %n_0
	%96 = call @MemMove(%92, %93, %94, %95)
	%97 = load %arr_0
	%98 = load %begin_pos_0
	%100 = load %n_0
	%101 = div %100, 2
	%102 = load %w_0
	%103 = load %w_0
	%104 = call @multiply(%102, %103)
	%105 = call @fft(%97, %98, %101, %104)
	%106 = load %arr_0
	%107 = load %begin_pos_0
	%109 = load %n_0
	%110 = div %109, 2
	%111 = add %107, %110
	%113 = load %n_0
	%114 = div %113, 2
	%115 = load %w_0
	%116 = load %w_0
	%117 = call @multiply(%115, %116)
	%118 = call @fft(%106, %111, %114, %117)
	@wn_0 = alloc i32
	store 1, @wn_0
	@i_2 = alloc i32
	store 0, @i_2
	jump %LLB_30

%LLB_30:
	%119 = load @i_2
	%121 = load %n_0
	%122 = div %121, 2
	%123 = lt %119, %122
	br %123, %LLB_31, %LLB_29

%LLB_31:
	@x_0 = alloc i32
	%124 = load %begin_pos_0
	%125 = load @i_2
	%126 = add %124, %125
	%127 = load %arr_0
	%128 = getptr %127, %126
	%129 = load %128
	store %129, @x_0
	@y_0 = alloc i32
	%130 = load %begin_pos_0
	%131 = load @i_2
	%132 = add %130, %131
	%134 = load %n_0
	%135 = div %134, 2
	%136 = add %132, %135
	%137 = load %arr_0
	%138 = getptr %137, %136
	%139 = load %138
	store %139, @y_0
	%140 = load %begin_pos_0
	%141 = load @i_2
	%142 = add %140, %141
	%143 = load %arr_0
	%144 = getptr %143, %142
	%145 = load @x_0
	%146 = load @wn_0
	%147 = load @y_0
	%148 = call @multiply(%146, %147)
	%149 = add %145, %148
	%150 = mod %149, 998244353
	store %150, %144
	%151 = load %begin_pos_0
	%152 = load @i_2
	%153 = add %151, %152
	%155 = load %n_0
	%156 = div %155, 2
	%157 = add %153, %156
	%158 = load %arr_0
	%159 = getptr %158, %157
	%160 = load @x_0
	%161 = load @wn_0
	%162 = load @y_0
	%163 = call @multiply(%161, %162)
	%164 = sub %160, %163
	%165 = add %164, 998244353
	%166 = mod %165, 998244353
	store %166, %159
	%167 = load @wn_0
	%168 = load %w_0
	%169 = call @multiply(%167, %168)
	store %169, @wn_0
	jump %LLB_28

%LLB_28:
	%170 = load @i_2
	%171 = add %170, 1
	store %171, @i_2
	jump %LLB_30

%LLB_29:
	ret 0
}


fun @main(): i32 {
%LLB_44:
	@n_1 = alloc i32
	%172 = getelemptr @a, 0
	%173 = call @getarray(%172)
	store %173, @n_1
	@m_0 = alloc i32
	%174 = getelemptr @b, 0
	%175 = call @getarray(%174)
	store %175, @m_0
	call @starttime()
	store 1, @d
	jump %LLB_35

%LLB_35:
	%176 = load @d
	%177 = load @n_1
	%178 = load @m_0
	%179 = add %177, %178
	%180 = sub %179, 1
	%181 = lt %176, %180
	br %181, %LLB_36, %LLB_34

%LLB_36:
	jump %LLB_33

%LLB_33:
	%182 = load @d
	%183 = mul %182, 2
	store %183, @d
	jump %LLB_35

%LLB_34:
	%184 = getelemptr @a, 0
	%185 = load @d
	%187 = load @d
	%188 = div 998244352, %187
	%189 = call @power(3, %188)
	%190 = call @fft(%184, 0, %185, %189)
	%191 = getelemptr @b, 0
	%192 = load @d
	%194 = load @d
	%195 = div 998244352, %194
	%196 = call @power(3, %195)
	%197 = call @fft(%191, 0, %192, %196)
	@i_3 = alloc i32
	store 0, @i_3
	jump %LLB_37

%LLB_37:
	%198 = load @i_3
	%199 = load @d
	%200 = lt %198, %199
	br %200, %LLB_39, %LLB_38

%LLB_39:
	%201 = load @i_3
	%202 = getelemptr @a, %201
	%203 = load @i_3
	%204 = getelemptr @a, %203
	%205 = load %204
	%206 = load @i_3
	%207 = getelemptr @b, %206
	%208 = load %207
	%209 = call @multiply(%205, %208)
	store %209, %202
	%210 = load @i_3
	%211 = add %210, 1
	store %211, @i_3
	jump %LLB_37

%LLB_38:
	%212 = getelemptr @a, 0
	%213 = load @d
	%215 = load @d
	%216 = div 998244352, %215
	%217 = sub 998244352, %216
	%218 = call @power(3, %217)
	%219 = call @fft(%212, 0, %213, %218)
	@i_4 = alloc i32
	store 0, @i_4
	jump %LLB_42

%LLB_42:
	%220 = load @i_4
	%221 = load @d
	%222 = lt %220, %221
	br %222, %LLB_43, %LLB_41

%LLB_43:
	%223 = load @i_4
	%224 = getelemptr @a, %223
	%225 = load @i_4
	%226 = getelemptr @a, %225
	%227 = load %226
	%228 = load @d
	%229 = call @power(%228, 998244351)
	%230 = call @multiply(%227, %229)
	store %230, %224
	jump %LLB_40

%LLB_40:
	%231 = load @i_4
	%232 = add %231, 1
	store %232, @i_4
	jump %LLB_42

%LLB_41:
	call @stoptime()
	%233 = load @n_1
	%234 = load @m_0
	%235 = add %233, %234
	%236 = sub %235, 1
	%237 = getelemptr @a, 0
	call @putarray(%236, %237)
	ret 0
}