#include<bits/stdc++.h>

typedef long long ll;
typedef long double ld;
using namespace std;
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 mrand(42);
#define ii for(int i=1;i<=n;++i)
#define ji for(int j=1;j<=n;++j)
#define jj for(int j=1;j<=m;++j)
#define ij for(int i=1;i<=m;++i)
#define sz(x) ((ll)x.size())
#define all(x) x.begin(),x.end()
#define al(x) x+1,x+1+n
#define asd cout<<"ok"<<endl;
#define asdd cout<<"okok"<<endl;
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define pr(v) for(auto i:v) cout<<i<<" ";cout<<endl;
#define prt(a, l, r) for(auto i=l;i<=r;++i) cout<<a[i]<<" ";cout<<endl;
#define pc(x) __builtin_popcount(x)
#define pb push_back
#define PS string qqwwee;cin>>qqwwee;
typedef pair<int, int> pii;

int p[4];
set<string> s[105];
void dfs(string t) {
    if(t.size() > 10) return;
    s[t.size()].insert(t);
    for(int i=1;i<t.size();++i) {
        int a = t[i-1] - '0', b = t[i] - '0';
        char c = p[a<<1|b] + '0';
        string nxt = t.substr(0, i) + c + t.substr(i);
        dfs(nxt);
    }
}
const int mod = 1e9+7;
ll fpow(ll a,ll b){ll r=1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}
ll fib(ll n) {
    function<ll(ll,ll,ll,ll,ll)> f = [&](ll a,ll b,ll p,ll q,ll n) -> ll {
        if(!n) return b;
        if(n&1) return f((b*q+a*q+a*p)%mod,(b*p+a*q)%mod,p,q,n-1);
        return f(a,b,(p*p+q*q)%mod,(q*q+2*q*p)%mod,n/2);
    };
    return f(1,0,0,1,n);
}
int main() {
    int n;
    cin >> n;
    if(n <= 3) return cout << 1 << endl, 0;
    for(int i=0;i<4;++i) {
        char c;
        cin>>c;
        p[i]=c-'A';
    }
    dfs("01");
    if(s[5].size() == 1) cout << 1 << endl;
    else if(s[5].size() == 4) cout << fpow(2, n-3) << endl;
    else cout << fib(n-1) << endl;
}
#pragma region templates
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using PQ = priority_queue<T>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007; // 998244353;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const ld PI = acos((ld)-1);
constexpr ll dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
inline void Yes() { cout << "Yes" << ENDL; }
inline void No() { cout << "No" << ENDL; }
inline void YES() { cout << "YES" << ENDL; }
inline void NO() { cout << "NO" << ENDL; }

template<typename T,typename Y> inline T mpow(T a, Y n) {
	T res = 1;
	for(;n;n>>=1) {
		if (n & 1) res = res * a;
		a = a * a;
	}
	return res;
}

template <typename T>
vector<T> finddivisor(T x) {  //整数xの約数(xを含む)
	vector<T> divisor;
	for(T i = 1; (i * i) <= x; i++) {
		if(x % i == 0) {
			divisor.push_back(i);
			if(i * i != x) { divisor.push_back(x / i);}
		}
	}
	sort(divisor.begin(), divisor.end());
	return divisor;
}

template <typename T> V<T> prefix_sum(const V<T>& v) {
	int n = v.size();
	V<T> ret(n + 1);
	rep(i, 0, n) ret[i + 1] = ret[i] + v[i];
	return ret;
}


template<typename T>
T rand(T l,T r){
	static random_device rd;
	static mt19937 g(rd());
	return uniform_int_distribution<T>(l,r)(g);
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
	for(auto&& x: vec) is >> x;
	return is;
}

template<typename T,typename Y>
ostream& operator<<(ostream& os,const pair<T,Y>& p){
	return os<<"{"<<p.fs<<","<<p.sc<<"}";
}

template<typename T> ostream& operator<<(ostream& os,const V<T>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

template<typename ...Args>
void debug(Args&... args){
	for(auto const& x:{args...}){
		cerr<<x<<' ';
	}
	cerr<<ENDL;
}
#pragma endregion templates


signed main(){
	cin.tie(0);cerr.tie(0);ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	ll k,n,m;cin>>k>>n>>m;
	ll rem=m;
	V<ll> a(k);cin>>a;

	PQ<tuple<ll,ll,ll>> p1,p2;
	V<ll> b(k,0);

	rep(i,0,k){
		ll num=a[i]*m/n;
		p1.emplace(1,num,i);
		p2.emplace(-n*(1+2*num)+2*a[i]*m,1,i);
	}

	while(rem>0){
		if(p1.size()){
			ll key,x,id;
			tie(key,x,id)=p1.top();
			p1.pop();
			b[id]+=min(rem,x);

			if(rem<x){
				rem=0;
			}else{
				rem-=x;
			}
		}else if(p2.size()){
			ll key,x,id;
			tie(key,x,id)=p2.top();
			p2.pop();
			b[id]+=min(rem,x);

			if(rem<x){
				rem=0;
			}else{
				rem-=x;
			}
		}else{
			b[0]+=rem;
			rem=0;
		}
	}
	for(auto&& i:b)cout<<i<<" ";
	cout<<ENDL;
}
//(・_・)(・_・)(・_・)(・_・)
//CHECK overflow,what to output?
//any other simpler approach?